OAI/Computability/LoopMatching/Approximation.lean

GitHub source file

11 declarations, 0 contain sorry, 0 declared as axioms

Polynomial-time approximation of weighted matchings with singleton loops.

  1. def OAI.LoopMatching.Approximation.term line 15
  2. def OAI.LoopMatching.Approximation.output line 18
  3. theorem OAI.LoopMatching.Approximation.term_bounds line 21
  4. theorem OAI.LoopMatching.Approximation.output_den_pos line 28
  5. theorem OAI.LoopMatching.Approximation.output_value line 30
  6. theorem OAI.LoopMatching.Approximation.factorial_profile_bounds line 35
  7. theorem OAI.LoopMatching.Approximation.output_bounds_of_expanded_count line 71
  8. theorem OAI.LoopMatching.Approximation.output_magnitude line 104
  9. theorem OAI.LoopMatching.Approximation.succ_le_two_pow line 110
  10. theorem OAI.LoopMatching.Approximation.factorial_le_two_pow_square line 118
  11. theorem OAI.LoopMatching.Approximation.output_exponential_magnitude line 130