Lemma 2.1 — exponential clocks separate and with probability at most
ProvedMultiwayCut.lemma_2_1approximation-algorithmsmultiway-cutp2o-gran-per-chapterp2o-plan-paperp2o-v1randomized-rounding
Let differ only in two coordinates , with and for some . Then the probability that the exponential clocks algorithm assigns and to different terminals satisfies
The paper quotes this bound from Buchbinder, Naor and Schwartz; it gives the exponential-clocks part of the cut density of Algorithm 3, and it holds at every , not only in the limit.
Differences from the source:
- encoding: the paper's coordinates and terminals , →
Fin kfrom , ; reason: Lean convention; the same statement after the index shift - encoding: probability over i.i.d. ; → measure of the event under the product of
expMeasure 1(outer measure); the argmin is taken over by cross-multiplication, ties to the least index; reason: in the paper, while Lean's would let a zero coordinate win; ties have probability
Preamble
import Mathlib import Definitions.Def_MultiwayCut_ExpClocks import Definitions.Def_MultiwayCut_CutDensity
Formal statement
namespace MultiwayCut
/-- **Lemma 2.1** (exponential clocks), Buchbinder, Schwartz & Weizman, *Simplex
Transformations and the Multiway Cut Problem*, manuscript of Nov. 1, 2016, p.3 (cited there
from [5]): given `u, v ∈ Δ_k` that differ only in coordinates `i` and `j`, where
`vᵢ = uᵢ + ε` and `v_j = u_j − ε` for some `ε ≥ 0`, the probability that `u` and `v` are
assigned to different terminals by the exponential clocks algorithm is at most
`ε (2 − uᵢ − u_j)`.
**Formalization Note.** Coordinates are `Fin k`, 0-based; `v = u + ε(eᵢ − e_j)` is
`ijShift u i j ε`; `i ≠ j` because the two coordinates are distinct. -/
theorem lemma_2_1 {k : ℕ} [NeZero k] (u v : Fin k → ℝ) (hu : u ∈ stdSimplex ℝ (Fin k))
(hv : v ∈ stdSimplex ℝ (Fin k)) (i j : Fin k) (hij : i ≠ j) (ε : ℝ) (hε : 0 ≤ ε)
(huv : v = ijShift u i j ε) :
sepExp u v ≤ ε * (2 - u i - u j) := by sorry
end MultiwayCut
Source
Buchbinder, Schwartz & Weizman, Simplex Transformations and the Multiway Cut Problem, manuscript of Nov. 1, 2016, Lemma 2.1, p.3
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.