line_min_matching_cost
def
OPT: the minimum, over all permutations sigma of the n items, of the matching cost sum_i |a_i - b_{sigma(i)}|.
Statement
noncomputable def line_min_matching_cost {n : ℕ} (a b : Fin n → ℝ) : ℝ
- Defined in
- arXiv:2611.05777 (Sublinear Metric Distortion for Matching), Sec. 1 and Sec. 6: one-sided matching of n agents to n items with ordinal rankings by distance; the probabilistic serial rule (optimal matching cost)
- Verified
- 05 Nov 2026
- Axioms
- none listed
- Used by 10
- line_min_matching_cost_leOPT is at most the cost of any perfect matching.
- probabilistic_serial_line_distortion_ge_sharpSharpness half of OP-1158: for every n >= 2 and every real c < n there are n agents and n items at real positions with positive minimum…
- probabilistic_serial_equispaced_distortion_two_agents_attainedFor n = 2 with equispaced items at 0 and 1, agents at 0 and 1/2 with ties broken toward the smaller-index item attain the harmonic…
- probabilistic_serial_equispaced_distortion_le_two_agentsFor two agents at real locations and two equispaced items at 0 and 1, the probabilistic serial cost under any distance preference profile…
- probabilistic_serial_line_distortion_le_of_item_wait_leIf on an instance (agents at a, items at b, distance rankings pref) every item's waiting cost is at most OPT, then the probabilistic…
- probabilistic_serial_equispaced_distortion_le_three_agentsFor three agents at real locations and three equispaced items at 0, 1, and 2, the probabilistic serial cost under any distance preference…
- probabilistic_serial_line_distortion_le_two_agentsCase n = 2 of OP-1158: for two agents at real positions a_0, a_1 and two items at real positions b_0, b_1, with each agent ranking the…
- probabilistic_serial_line_cost_le_add_item_waitFor n agents at real positions a and n items at real positions b, each agent ranking the items by distance (ties broken arbitrarily), the…
- line_min_matching_cost_nonnegOPT is nonnegative.
- probabilistic_serial_line_distortion_le_three_agentsCase n = 3 of OP-1158: for three agents at real positions a_0, a_1, a_2 and three items at real positions b_0, b_1, b_2, with each agent…
Read back from the Lean
For an implicit natural number $n$ and two functions $a, b : \mathrm{Fin}\ n \to \mathbb{R}$, line_min_matching_cost a b is defined as the minimum (infimum over the nonempty finite set of all permutations $\sigma$ of $\mathrm{Fin}\ n$) of the sum $\sum_{i \in \mathrm{Fin}\ n} |a(i) - b(\sigma(i))|$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- Minimum cost `min_σ ∑ i, |a i - b (σ i)|` of a perfect matching of agents at `a` to items at `b` on the line. -/ noncomputable def line_min_matching_cost {n : ℕ} (a b : Fin n → ℝ) : ℝ := Finset.univ.inf' Finset.univ_nonempty (fun σ : Equiv.Perm (Fin n) => ∑ i, |a i - b (σ i)|)