Lemma 5.4 — CKR after the matrix (5.3) has cut density
ProvedMultiwayCut.lemma_5_4approximation-algorithmsmultiway-cutp2o-gran-per-chapterp2o-plan-paperp2o-v1randomized-rounding
Let be the transformation (5.1) with the matrix of (5.3). For every , every with and every , the cut density at of CKR executed on , for edges of type , satisfies
Combined with Lemma 2.1 and it yields the overall density of Theorem 1.2.
Differences from the source:
- encoding: the paper's coordinates and terminals , →
Fin kfrom , ; reason: Lean convention; the same statement after the index shift - reading: edges of type with (the paper's standing "without loss of generality", pp.5–6) → the -edge in the identity order, non-increasing in
Fin k; reason: exactly the paper's normalization; other orders follow by renaming coordinates - encoding: → for every , eventually as , the ratio is at most , for those at which is an -edge; reason: the same condition; an edge has , and
Filter.limsupin returns a junk value on unbounded functions - reading: the matrix (5.3) printed with "…" for a general →
A53 kfor every , defined by the entry formula (the top-left block of the printed pattern); reason: the paper never restricts ; this is the only matrix consistent with the printed pattern
Preamble
import Mathlib import Definitions.Def_MultiwayCut_CKR import Definitions.Def_MultiwayCut_CutDensity import Definitions.Def_MultiwayCut_Transformation import Definitions.Def_MultiwayCut_A53
Formal statement
namespace MultiwayCut
/-- **Lemma 5.4**, Buchbinder, Schwartz & Weizman, *Simplex Transformations and the Multiway
Cut Problem*, manuscript of Nov. 1, 2016, p.8: the cut density of Algorithm 2 executed after
applying the transformation defined by the matrix (5.3) satisfies
`α_{i,j} ≤ 44/27 (uᵢ + u_j) + 55/108 Σ_{ℓ≠i,j} u_ℓ`.
**Formalization Note.** For every `k ≥ 1`, at a sorted `u` (the paper's standing "without loss
of generality"; the `(i, j)`-edge's order is the identity), positions `i < j : Fin k` 0-based.
The cut density is `IJDensityLE` (Definition 2.1) of `Pr_CKR[f(u), f(v) separated]` with
`f = quadTransform (A53 k)`. -/
theorem lemma_5_4 {k : ℕ} [NeZero k] (u : Fin k → ℝ) (i j : Fin k) :
IJDensityLE (fun x y => sepCKR (quadTransform (A53 k) x) (quadTransform (A53 k) y))
(Equiv.refl (Fin k)) i j u
(44 / 27 * (u i + u j) + 55 / 108 * ∑ ℓ ∈ Finset.univ \ {i, j}, u ℓ) := by sorry
end MultiwayCut
Source
Buchbinder, Schwartz & Weizman, Simplex Transformations and the Multiway Cut Problem, manuscript of Nov. 1, 2016, Lemma 5.4, p.8 (proof pp.8–11)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.