diff 56bc728..f6bf760 metric_k_median_threshold_v2.txt
diff --git a/metric_k_median_threshold_v2.txt b/metric_k_median_threshold_v2.txt
index 9c58253..0e23278 100644
--- a/metric_k_median_threshold_v2.txt
+++ b/metric_k_median_threshold_v2.txt
@@ -1,46 +1,4 @@
THE APPROXIMATION THRESHOLD FOR METRIC k-MEDIAN
-A complete proof
-================================================================
-
-CONTENTS
- 1. The problem
- 2. Approximation ratio
- 3. The main theorem
- 4. Hardness: 1 + 2/e is a lower bound
- 5. Road map of the proof
- 6. Stage 1: The LP and nearest-unit cost
- 7. Stage 2: Preparation (grid rounding)
- 8. Stage 3: The finite comparison inequality
- 9. Scalar bounds
- 10. Stage 4: Tapered iterative rounding
- 11. Stage 5: Derandomization
- 12. Stage 6: Removing the surplus
- 13. Assembly: proof of the main theorem
- Appendix A. Certificates for the scalar bounds
- Appendix B. Glossary
-
-
-PREFACE
--------
-
-This document proves one theorem and its matching hardness bound.
-The proof is complete: every lemma is either proved from
-scratch or is a well-known external result stated precisely.
-
-The one sentence version:
-
- For every eps > 0, there is a deterministic polynomial-time
- algorithm that, on every finite rational metric k-median
- instance, finds a set of at most k facilities whose total
- connection cost is at most (1 + 2/e + eps) times the best
- possible, and assuming P != NP no deterministic polynomial-time
- algorithm can promise a factor strictly below 1 + 2/e.
-
-Here e = 2.71828... is Euler's number, so 1 + 2/e = 1.7358...
-Read on for the definitions.
-
-
-=============================
1. THE PROBLEM
=============================
@@ -244,72 +202,6 @@ problem changes; the threshold 1 + 2/e is not known to apply there
(Anand and Lee, 2024, study the supplier version).
-=============================
-5. ROAD MAP OF THE PROOF
-=============================
-
-The proof of Theorem 1.1 is a chain of stages. Each stage takes a
-"nice" fractional solution as input, produces a "cleaner" one as
-output, and adds an amount that can be made arbitrarily small
-(we can shake eta, tau, zeta, phi, eps down to zero). The stages
-are:
-
- Stage 1 (Section 6). Solve the LP relaxation of k-median. Its
- value L is at most OPT_k, and there is a per-client fractional
- cost V_j with sum_j V_j <= L <= OPT_k. This is our starting
- point: from now on, "close to optimal" means "close to
- sum_j V_j".
-
- Stage 2 (Section 7). Snap the fractional openings to a grid of
- spacing g = 1/Delta, where Delta is a sufficiently large
- constant depending only on the accuracy we want. Total opening
- mass increases by at most 3g. Each V_j increases by only a
- factor of at most (1 + eta), for any fixed eta > 0 we choose.
-
- Stage 3 (Sections 8 and 9). Prove a purely algebraic inequality
- on finite probability spaces - the FINITE COMPARISON INEQUALITY.
- It is the engine of the cost accounting. Section 8 proves the
- inequality given certain scalar bounds; Section 9 states those
- bounds and Section 9 + Appendix A verify them with exact rational
- certificates.
-
- Stage 4 (Section 10). TA PERED ITERATIVE ROUNDING. Take the grid
- solution and simulate k-median's rounding as a sequence of
- "rounds". Each round has a directed graph on copies of the
- opened facilities, some are selected at random to open, others
- to erase. A potential tracks the cost for one client. The drift
- is controlled by the finite comparison inequality. Result: at
- most k + c facilities (c a constant), expected cost at most
- (1 + 2/e + tau) sum_j V_j. Randomness used.
-
- Stage 5 (Section 11). DERANDOMIZATION. The Stage 4 analysis used
- only finitely many low-order moments of the random choices (first
- and second moments, occasionally fourth). Replace each
- independent coin by a polynomial-size list of weighted outcomes
- that preserves exactly these moments (a Caratheodory-type
- argument). Select the cheapest output subject to the additive
- opening budget. Result: a genuinely deterministic algorithm
- opening at most k + c facilities with cost at most
- (1 + 2/e + eps) OPT_k.
-
- Stage 6 (Section 12). APPLY THE LI-SVENSSON REDUCTION. Any
- deterministic c-additive alpha-approximation converts to an
- ordinary (alpha + eta)-approximation opening at most k
- facilities, at the cost of an n^{O(c/eta)} poly factor in the
- running time. For fixed c, eta this is polynomial time.
-
- Assembly (Section 13). Chain the stages: run Stage 2-5 with
- internal loss eps/4, then Stage 6 with loss eps/2, to get exact
- factor 1 + 2/e + eps. Done.
-
-The new ingredient compared to prior work is Stages 3-4: a
-potential whose coefficient is tuned to the elapsed time, coupled
-to a DIRECTED comparison inequality. Prior iterative-rounding
-arguments bottomed out at factor 2 because their transfer lemma
-required symmetric or otherwise weaker comparison. The directed
-version drives the constant down to 1 + 2/e.
-
-
=============================
6. STAGE 1: THE LP AND NEAREST-UNIT COST
=============================