p.4 — cut density gives approximation (corrected: uniform remainder instead of )
ProvedMultiwayCut.karger_reductionapproximation-algorithmsmultiway-cutp2o-correctedp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1randomized-rounding
The paper states (p.4): "As in Karger et al. [21], it is easy to show that any randomized algorithm for Multiway Cut achieves an approximation of ." With the cut density of Definition 2.1 this is false; the following corrected form holds.
Let be a function on with , and ; every separation probability of a randomized labeling has these properties (the third is the union bound). Let and suppose there is a constant such that for every -edge with parameter , in any order of the coordinates and for any ,
Then
- for all ;
- for every instance and every feasible embedding of the simplex relaxation,
i.e. the expected weight of the cut is at most times the relaxation's objective.
Differences from the source:
- correction: cut density defined by → a bound on every -edge, with independent of the edge; reason: the printed statement is false: for the deterministic labeling iff or (else ) labels the terminals correctly and has , yet on the unit-weight path with at (an optimal relaxation solution of value ) it cuts edges
- generalization: a randomized algorithm (a distribution over labelings) → any function on vanishing on the diagonal, symmetric and satisfying the triangle inequality; reason: every separation probability has these properties, so the statement specializes to the paper's
- reading: "achieves an approximation of " → the expected cut weight is at most times the relaxation objective of every feasible embedding (and the pointwise bound ); reason: this is the guarantee the paper derives from cut density; at an optimal embedding the objective is at most the optimum cut
- encoding: expected weight of the cut → ; reason: linearity of expectation
Preamble
import Mathlib import Definitions.Def_MultiwayCut_Instance import Definitions.Def_MultiwayCut_CutDensity
Formal statement
namespace MultiwayCut
/-- **Cut density bounds the approximation ratio** (corrected), Buchbinder, Schwartz & Weizman,
*Simplex Transformations and the Multiway Cut Problem*, manuscript of Nov. 1, 2016, p.4: "As in
Karger et al. [21], it is easy to show that any randomized algorithm for Multiway Cut achieves
an approximation of `γ = max_{1≤i<j≤k} {γ_{i,j}}`."
Corrected form. Let `s u v` be the probability `Pr[g(u) ≠ g(v)]` that a randomized labeling
separates `u` and `v`; it vanishes on the diagonal, is symmetric and obeys the union bound
`s u w ≤ s u v + s v w` on `Δ_k` (every separation probability does). If on every `(i, j)`-edge
(any order `π`, any `i < j`) with parameter `ε` the separation probability is at most
`γ ε + C ε²` for one constant `C` independent of the edge, then `s u v ≤ γ · ½ ‖u − v‖₁` for all
`u, v ∈ Δ_k`, and hence the expected weight of the cut is at most `γ` times the relaxation's
objective on every instance and every feasible embedding.
**Formalization Note.** The printed statement uses the lim sup cut density of Definition 2.1,
under which it is false (a deterministic `k = 2` labeling of density `0` that cuts `3` edges of
an optimal path solution of value `1`; see the natural-language statement); the
uniform second-order remainder `C ε²` is the correction. `γ` bounds every `γ_{i,j}`. The
expected cut weight is `Σ_{e∈E} w_e · s(x_u, x_v)` by linearity of expectation. -/
theorem karger_reduction {k : ℕ} (s : (Fin k → ℝ) → (Fin k → ℝ) → ℝ) (γ : ℝ)
(hdiag : ∀ u ∈ stdSimplex ℝ (Fin k), s u u = 0)
(hsymm : ∀ u ∈ stdSimplex ℝ (Fin k), ∀ v ∈ stdSimplex ℝ (Fin k), s u v = s v u)
(htri : ∀ u ∈ stdSimplex ℝ (Fin k), ∀ v ∈ stdSimplex ℝ (Fin k),
∀ w ∈ stdSimplex ℝ (Fin k), s u w ≤ s u v + s v w)
(hedge : ∃ C : ℝ, ∀ (π : Equiv.Perm (Fin k)) (i j : Fin k) (ε : ℝ) (u v : Fin k → ℝ),
IsIJEdge π i j ε u v → s u v ≤ γ * ε + C * ε ^ 2) :
(∀ u ∈ stdSimplex ℝ (Fin k), ∀ v ∈ stdSimplex ℝ (Fin k), s u v ≤ γ * halfL1 u v) ∧
∀ {V : Type} [Fintype V] (I : Instance V k) (x : V → Fin k → ℝ),
IsFeasibleEmbedding I x →
∑ e ∈ I.E, I.w e * s (x e.1) (x e.2) ≤ γ * relaxValue I x := by sorry
end MultiwayCut
Source
Buchbinder, Schwartz & Weizman, Simplex Transformations and the Multiway Cut Problem, manuscript of Nov. 1, 2016, p.4 (§2.4, "As in Karger et al. [21], it is easy to show that any randomized algorithm for Multiway Cut achieves an approximation of γ = max γ_{i,j}")
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.