PaperlayerView exact revision on arXiv

Source-linked AI summary

A (Slightly) Improved Approximation Algorithm for Metric TSP

Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan

arXiv:2007.01409v6cs.DSmath.COmath.PR

TL;DR

Metric TSP asks for a minimum-cost Hamiltonian cycle under triangle-inequality distances, and the paper studies how far its approximation guarantee can be improved. It uses a cactus-case reduction with slack in OPT to give a randomized 3/2 − 3 × 10^-36 approximation algorithm.

  • Problem

    The paper asks how far metric TSP’s approximation guarantee can be improved, for a problem described as fundamental in combinatorial optimization.

    Source: §1 · p. 3

  • Method

    The approach uses a cactus-case reduction with a slack vector for OPT and OPT edges in the construction.

    Source: §3.1 · p. 24

  • Results

    3/2 − 3 × 10^-36 approximation: the paper gives a randomized algorithm for metric TSP.

    Source: §1 · p. 3, §3 · p. 21

  • Takeaways & Limitations

    The authors characterize the result as a very slight improvement to the TSP approximation guarantee.

    Source: §3.1 · p. 24

    The proof requires 28η ≪ ε, forcing η to be very small and limiting the improvement to a very slight one.

    Source: §3.1 · p. 24

Abstract

from arXiv · show

For some $ε> 10^{-36}$ we give a randomized $3/2-ε$ approximation algorithm for metric TSP.

1 Introduction

The paper gives a randomized expected-cost approximation for metric TSP with ratio 3/2 − ε for some ε > 10^-36, and develops new technical tools alongside the algorithm.

1 Introduction

  • For some absolute ε > 10^-36, a randomized algorithm outputs a tour with expected cost at most (3/2 − ε) times the cost of the optimum solution.The authors do not prove that the Held–Karp polytope’s integrality gap is bounded away from 3/2, and report no known example where the algorithm’s approximation ratio exceeds 4/3 in expectation.Source: §1 · p. 3
  • A randomized algorithm also finds a TSP path with expected cost at most (3/2 − ε) times optimum for some absolute ε > 0.The authors derive this result following work by Traub, Vygen, and Zenklusen [TVZ20].Source: §1 · p. 3

1.1 Algorithm

  • The algorithm samples a spanning tree from a λ-uniform distribution whose edge marginals approximately match an optimum TSP relaxation, then adds a minimum-cost matching on odd-degree vertices.The algorithm is a slight modification of the one proposed in.Source: §1.1 · pp. 3–4

1.2 New Techniques

  • The paper presents new machinery and technical tools developed for the result, which the authors say could be of independent interest.Source: §1.2 · p. 4

1.2.1 Polygon Structure for Near Minimum Cuts Crossed on one Side.

  • For a special polygon representation of near-minimum cuts, the paper bounds each atom’s cut weight by 2 + O(η) and each adjacent-atom edge weight below by 1 − Ω(η).The representation has no atoms mapped inside the polygon, and the relevant intervals are crossed only on one side.Source: §1.2.1 · p. 5

1.2.2 Generalized Gurvits’ Lemma

  • For strongly Rayleigh distributions, the paper generalizes a result on simultaneous exact counts: when the expected counts differ from one by total less than 1 − ε, the all-ones event has probability at least f(ε, m), independent of n.The proof has double-exponential dependence on ε, and finding the optimal dependence is left open.Source: §1.2.2 · p. 6

1.2.3 Conditioning while Preserving Marginals

  • For two disjoint sets with expected counts approximately one, an event within the event that both counts equal one has probability at least Ω(α^2) and almost preserves their element marginals.The quadratic dependence on α is necessary for sufficiently small α.Source: §1.2.3 · pp. 6–7

2 Preliminaries

This section introduces the graph, cut, and polyhedral notation used in the paper and collects bounds for Bernoulli sums and structural facts about near-minimum cuts. It also examines how conditioning on such cuts affects random spanning-tree distributions, including conditional edge and degree behavior.

2.1 Notation

  • For G=(V,E,x), cuts have weight x(δ(S)), an η-near min cut has weight at most 2+η, and cuts are assumed to exclude terminals u0,v0.The section also defines when vertex sets cross.Source: §2.1 · p. 7

2.2 Polyhedral Background

  • Edmonds characterizes the spanning-tree polytope, and restricting a feasible Held-Karp solution to the original edges gives a point in that polytope.The polytope’s extreme points are characteristic vectors of spanning trees.Source: §2.2 · p. 8
  • The algorithm’s analysis seeks a random vector y satisfying all cuts with expected cost at most (1/2−ε)OPT; the O-join polytope characterizes the matching cost used in that analysis.A satisfied-cut condition is defined for a vertex set and a spanning tree.Source: §2.2 · p. 8

2.3 Structure of Near Minimum Cuts

  • Crossing εA- and εB-near minimum cuts have intersection, union, and both set differences that are (εA+εB)-near minimum cuts.The result follows from cut-weight submodularity and the lower bound of 2 on the other cut.Source: §2.3 · p. 9

2.4 Strongly Rayleigh Distributions and λ-uniform Spanning Tree Distributions

  • Strongly Rayleigh distributions are closed under projection, conditioning, truncation, and products, but not necessarily under truncating a specified subset to exactly k elements.These operations are repeatedly used in the paper.Source: §2.4 · p. 10
  • Conditioning a λ-uniform spanning-tree distribution on an edge or on a vertex set being a tree preserves that distribution class, and tree conditioning yields a crucial independence property.Arbitrary spanning-tree distributions need not be closed under truncation and projection.Source: §2.4 · p. 10
  • Strongly Rayleigh measures are negatively associated, and their rank sequences are sums of independent Bernoullis, hence log-concave and unimodal with mode less than 1 from the mean.Source: §2.4 · pp. 11–12

2.5 Sum of Bernoullis

  • Hoeffding’s theorem characterizes extremal independent-Bernoulli sums, and the section also gives a parity-probability bound for BS(q) when 0<q≤1.2.Source: §2.5 · p. 13
  • If a Bernoulli sum X equals integer k with probability at least 1−ε, where ε<1/10, its parameter q satisfies k(1−ε) ≤ q ≤ k(1+ε)+3ε.Source: §2.5 · p. 14

2.6 Random Spanning Trees

  • For an ε-near-minimum cut S excluding e0’s endpoints, P[S is a tree] ≥1−ε/2; under max-entropy, conditioning on S being a tree shifts expected A- and B-edge counts by at most ε/2 in opposite directions.The conditioned A-edge expectation is between its unconditional value and that value plus ε/2; the conditioned B-edge expectation is between its unconditional value minus ε/2 and that value.Source: §2.6 · pp. 16–17
  • For disjoint near-minimum cuts A and B, all of A, B, and A∪B are trees with probability at least 1−(εA+εB+εA∪B)/2, implying exactly one edge between A and B.Source: §2.6 · p. 17
  • In a λ-uniform spanning-tree distribution, conditioning on edge e being absent raises the expected degree of w by at most P[w lies on the u-v tree path | e absent]·P[e is included].Here e=(u,v), w is distinct from u and v, and the degree counts incident tree edges.Source: §2.6 · p. 17
  • If adjacent edges e and f each have inclusion probability within ε of 1/2, for ε<1/1000, the conditional expected degrees at their opposite endpoints sum to at most the unconditional sum plus 0.81.Here the counted edge sets are U=δ(u)−e and W=δ(w)−f, conditioned respectively on e and f being absent.Source: §2.6 · p. 18

3 Overview of Proof

The proof bounds the expected cost of the sampled tree’s minimum-cost matching by constructing a cheap feasible O-join and controlling its expected slack. It organizes near-min-cuts into a hierarchy and uses reductions and matching arguments to handle bad edges, triangle cuts, bottom-edge interactions, and extreme values of x_u while preserving the O-join constraints.

3 Overview of Proof

  • The proof seeks a feasible O-join of expected cost at most OPT(1/2 − ε) by exploiting even cuts in the sampled tree and reducing edge slack below x_e/2.It starts with y_e = x_e/2, then uses a random slack vector whose expected value is negative for LP edges.Source: §3 · pp. 19–20
  • 3/2 − 3·10^-36 is the approximation factor obtained for metric TSP.The proof derives the algorithm’s bound by choosing β = η/4.1 = ε_P/5362.8, with ε_P = 3.12·10^-16.Source: §3 · p. 21

3.1 Ideas underlying proof of Theorem 3.1

  • Theorem 3.2 gives a slack vector for hierarchy cuts that satisfies every unhappy cut and has expected slack at most −β ε_P x_e for each LP edge e ≠ e0.The hierarchy consists of degree cuts and triangle cuts.Source: §3.1 · p. 22
  • Each polygon’s near-min-cuts form unions of consecutive atoms whose neighboring pairs have x-edge value approximately 1, giving the cuts a cycle-like structure.The structure follows by partitioning one-sided crossing cuts into two laminar families.Source: §3.1 · p. 23
  • Non-hierarchy near-min-cuts are handled with nonnegative slack on OPT edges, with expected slack O(η²) per edge; the proof’s tiny η also prevents a new integrality-gap bound.Using OPT edges is necessary in this reduction, and 2^8η ≪ ε forces η to be very small.Source: §3.1 · p. 24

3.2 Proof ideas for Theorem 3.2

  • For top-edge bundles, edges are reduced when both top cuts are even, and slack on other bundles compensates when an odd cut would otherwise be left unsatisfied.The goal is for each bundle’s expected reduction to exceed its expected increase.Source: §3.2 · p. 24
  • When ε ≤ x_u,x_v ≤ 1−ε, conditioning on a reduction bounds the probability that δ(u)_T is odd by 1−O(ε), supporting negative expected slack.This uses the independent-trees property for a cut of value 2 and the Strong Rayleigh property.Source: §3.2 · p. 25
  • The ideal-case analysis makes each edge’s reduction probability equal and uses the matching balance to show expected reductions exceed increases, which would yield an O-join cost at most (1/2 − ε)OPT.The paper defines a k-ideal reduction when each cut among the top k levels containing a reduced edge is odd with probability bounded away from 1.Source: §3.2 · p. 26
  • For every hierarchy cut u, at least 3/4 of the fractional mass in δ(u) is good, and these edges suffice to compensate for reductions on edges going higher.A matching pairs good edge bundles e=(u,v) with fractions m_e,u and m_e,v of edges in δ↑(u) and δ↑(v), respectively, with m_e,u + m_e,v roughly (1 + O(ε^1/2))x_e.Source: §3.2 · p. 27
  • The triangle-edge rules use 2-1-1 reductions and, for certain pairs of half edges, 2-2-2 reductions that decrease both bundles simultaneously.Non-half-edge bundles are 2-1-1 good; if two half edges lie in the same side, at least one is 2-1-1 good. The resulting rules are developed in Section 5.Source: §3.2 · p. 28
  • Bottom-edge reductions use βx_f versus τx_e, with β > τ, and preserving marginals when A_T = B_T = 1 makes the reduction ∞-ideal.The expected slack reduction holds when 2τq < β − ε; the overview sets τ = 0.571β and uses stronger bounds on lower-cut parity probabilities.Source: §3.2 · pp. 28–29
  • For triangle bottom edges, simultaneous reductions in edge bundles let one slack increase repair both odd cuts, while preserved marginals control the probability that a lower triangle is happy.In the consecutive-level example, that conditional probability is α² + (1 − α)².Source: §3.2 · p. 29
  • When x_u is close to 1, the proof separates edges ending at different hierarchy levels or applies a 2-1-1 rule to edges concentrated at one level.In the latter case, the degree cut is treated as a pseudo-triangle, with edge sets A and B chosen from disjoint cuts having sufficient fractional mass.Source: §3.2 · p. 30

4 Polygons and the Hierarchy of Near Minimum Cuts

This section develops structural and probabilistic tools for polygons and near-minimum cuts, including happy polygons, odd tree-cut corrections, and a hierarchy supporting edge-payment corrections. It also establishes notation for treating polygons as triangles and working with edge bundles.

4.1 Cuts Crossed on Both Sides

  • For η < 1/100, Theorem 4.2 constructs random nonnegative OPT-edge slacks that offset any s with s_e ≥ −x_eβ on odd tree-crossed near-minimum cuts crossed on both sides; P[I2(e*)] ≤ 18η.Source: §4.1 · pp. 32–33

4.3 Structure of Polygons of Cuts Crossed on One Side

  • For εη ≥ 14η, every pair of adjacent polygon atoms has x(E(ai, ai+1)) ≥ 1 − εη, so polygon structure approaches an integral cycle as η → 0.Source: §4.3 · pp. 36–37
  • The left and right hierarchies partition one-side-crossed cuts into laminar families, and each strict parent-child pair has a cut in the opposite hierarchy crossing both.Source: §4.3 · pp. 37–38
  • Any two disjoint cuts in either hierarchy have a common ancestor; each left and right hierarchy has a unique cut with no ancestors, and such cuts lie at the corresponding polygon endpoint.Source: §4.3 · pp. 38–39
  • For a polygon, x(δ(a1 ∪· · · ∪am−1)) ≤2 + 4η, and each root-neighbor edge set has x-value at least 1 −2η.The root-neighbor bounds apply to E(a0, a1) and E(a0, am−1).Source: §4.3 · p. 39
  • Every atom ai has x(δ(ai)) ≤2 + 14η, while each consecutive pair ai, ai+1 has x(δ({ai, ai+1})) ≤2 + 12η and x(E(ai, ai+1)) ≥1 −6η.Source: §4.3 · pp. 39–40

4.4 Happy Polygons

  • For happy polygons, odd tree cuts in C′ receive a correction making s(δ(S)) + s*(δ(S)) ≥0; the same holds for non-extreme cuts and atoms in C′.The theorem provides a random vector s* for a spanning-tree distribution with marginals x, for any s satisfying se ≥−βxe; the second guarantee excludes leftmost and rightmost cuts and atoms.Source: §4.4 · p. 41
  • For every cut A that is neither leftmost nor rightmost, P[δ(A)T = 2] ≥1 −22η.Source: §4.4 · p. 42
  • Cuts in C′ map to OPT edges e*2, . . . , e*m−1 so that each edge receives at most four cuts, and every polygon atom maps to two edges.An OPT edge is mapped to a cut only if it belongs to that cut's boundary.Source: §4.4 · p. 42
  • An η-near-minimum leftmost or rightmost cut is happy with probability at least 1 −10η; a qualifying leftmost or rightmost atom is happy with probability at least 1 −24η.Source: §4.4 · p. 43
  • 1−24η is a lower bound on the probability that atom a1 is happy.The bound follows by a union bound on the two events required for a1 to be happy.Source: §4.4 · p. 43

4.5 Hierarchy of Cuts and Proof of Theorem 4.6

  • The maximum-entropy payment theorem constructs a random edge vector that makes z/2 + s essentially feasible across the hierarchy while giving many good edges negative expected payments.The theorem applies when εη ≤ 10^-10 and β > 0; its good-edge and cut-payment conditions include lower bounds on se and payment inequalities for non-happy polygon cuts.Source: §4.5 · p. 46
  • 14η-near-minimum cuts crossed on at most one side are organized into a valid hierarchy of polygon and degree cuts, with every cut the union of its children.The construction processes connected components of such cuts along the OPT cycle, adding individual cuts or polygon atoms and their union.Source: §4.5 · p. 46
  • For every η-near-minimum cut S of z, odd δ(S)T implies s(δ(S)) + s*(δ(S)) ≥ 0; good edges also satisfy E[se] ≤ −εPβxe.Theorem 4.6 additionally bounds se below by −xeβ on good edges and sets it to zero elsewhere.Source: §4.5 · p. 47
  • The remaining cut cases use Theorem 4.24, with Lemma 4.25 for Type 5 atoms when the triangle is left-happy; C may intersect δ(S) unpredictably.For a leftmost cut, A is always contained in δ(S), but in the worst case only edges of C with negative slack belong to δ(S).Source: §4.5 · p. 48

4.6 Hierarchy Notation

  • From this point on, polygons can be treated as triangles, and edge bundles collect actual graph edges assigned to a degree-cut atom pair or a polygon cut.A top bundle contains edges whose endpoints lie in the specified atoms and whose parent is the degree cut; a bottom bundle contains edges whose parent is the polygon cut.Source: §4.6 · p. 48
  • The notation distinguishes edges between atoms of a cut from all edges between its vertices, and defines bundle values as the sum of their fractional edge values.It also uses F−e and F+e for removing or adding a bundle, respectively.Source: §4.6 · p. 48

5 Probabilistic statements

This section develops probabilistic guarantees for exact counts and for good- and happy-edge events, including edge pairs and adjacent half-edge bundles. It also uses a max-flow event to condition on two sets each having count one while approximately preserving edge marginals, with consequences for polygon cuts and their ancestors.

5.1 Gurvits’ Machinery and Generalizations

  • For m disjoint sets under an SR distribution, Proposition 5.1 lower-bounds the probability that every count equals its target by f(ε) times the probability their sum equals the target sum.The stated bound is f(ε) ≥ ε^(2m) ∏_{k=2}^m 1/(max{n_k, n_1 + ··· + n_{k−1}} + 1).Source: §5.1 · p. 49
  • In applications of Proposition 5.1, bounds on expected counts for every subset within one of its target suffice; the stated lower bound on f(ε) is not tight.The authors expect the dependence on m to be only exponential and leave finding a tight bound as an open problem.Source: §5.1 · p. 49

5.2 Max Flow

  • With 330ε < ζ < 0.002, a max-flow event has probability at least 0.0246ζ^2(1 − ζ/2.1 − ε) and ensures AT = BT = 1 while preserving edge marginals up to total variation ζ.The sets A and B are disjoint, and their expected counts must each lie in [1 − ε, 1 + ε].Source: §5.2 · pp. 52, 54
  • Conditioned on the max-flow event, edge marginals on δ(S) are preserved within εM + εη, and specified edge subsets have a Bernoulli-sum law with parameter near x(F).For F ⊆ E(S) ∪ δ(S) with F ∩ A = ∅ or F ∩ B = ∅, the parameter is q ∈ x(F) ± (εM + 2εη).Source: §5.2 · p. 55
  • For an ancestor polygon cut u, the section reports P[u not left happy | ES] ≤ 0.56797 and says conditioning on ES decouples δ(S)T from δ(u)T.The motivation notes that conditioning on δ(S)T alone may substantially change the distribution of δ(u)T, including its parity.Source: §5.2 · pp. 55–56
  • The same result also follows for right-happy.Source: §5.2 · p. 56

5.3 Good Edges

  • For a good half-edge bundle, each of P[AT + BT ≤ 2 | u, v trees] and P[AT + BT ≥ 4 | u, v trees] is at least 0.4ε1/2 under the stated parameter conditions.Source: §5.3 · p. 57
  • 3ε1/2 lower-bounds the probability that both endpoint degrees equal 2, conditioned on u and v being trees, under Lemma 5.16's stated assumptions.The bound follows from a probability of at least 0.5·6ε1/2 after additionally conditioning on S and W being trees.Source: §5.3 · pp. 57–58
  • At least one of two adjacent half-edge bundles is 2-2 good when ε1/2 < 0.0005 and εη ≤ ε1/2^2.Source: §5.3 · p. 59

5.4 2-1-1 and 2-2-2 Good Edges

  • For xe ≤ 1/2 − ε1/2 and xe ≥ 1/2 + ε1/2, respectively, a top edge bundle is 2-1-1 happy with probability at least 0.005ε1/2^2 and 0.006ε1/2^2.Both bounds assume ε1/2 ≤ 0.001; the second is happiness with respect to u.Source: §5.4 · p. 62
  • If two good half top edge bundles satisfy xe(B), xf(B) ≤ ε^1/2, at least one is 2-1-1 happy with probability at least 0.005ε^2.The bundles share endpoint v, and the lemma assumes the stated degree partition of δ(v).Source: §5.4 · p. 62
  • At most 1/2 + 4ε^1/2 of the good edges in A→ are not 2-1-1 good with respect to u.This bound applies for a degree cut S∈H and u∈A(S); limiting bad edges in each cut matters because they cannot be matched to edges going higher in the matching lemma.Source: §5.4 · p. 62
  • When two such bundles are 2-2-2 good, reducing them simultaneously lets a bottom edge increase by the larger decrease rather than the sum, saving a factor of 2.This handles the extreme case where both bundles are not 2-1-1 good and the A and B portions of the cut are each approximately 1/2.Source: §5.4 · p. 63
  • With ε^1/2 ≤ 0.0002, two good top half edge bundles that are not 2-1-1 good are 2-2-2 happy with probability at least 0.01 under the lemma’s stated conditions.2-2-2 happy means the three endpoints have T-degree 2 and are all trees; the pair is 2-2-2 good when its happiness probability is at least p.Source: §5.4 · p. 63
  • Theorem 5.28 guarantees either at least a 1/2 − ε^1/2 − εη fraction of δ→(v) is 2-1-1 good, or a pair of top half edge bundles is 2-2-2 good.The theorem states these as alternatives under its stated parameter constraints.Source: §5.4 · p. 63

6 Matching

This section constructs a matching to decide which edges receive positive slack to compensate for negative slack on edges going higher. The Matching Lemma matches good edge bundles to fractions of higher edges incident to their endpoints.

6 Matching

  • The Matching Lemma matches good edge bundles in E→(S) to fractions of higher edges at their endpoints, under stated bounds on ε_F, ε_B, α, and ε_1/2.Its proof sets up a max-flow min-cut problem.Source: §6 · pp. 64–65
  • The parameter F_u allows some good edges to be matched above their fraction in δ(S), while Z_u doubles matches to δ↑(u) when x(δ↑(u)) is near zero to ease parity correction.Only good edges are used because bad edges are not reduced in the payment theorem.Source: §6 · p. 64
  • When |A(S)| = 3, there are no bad edges in E→(S).Source: §6 · p. 65
  • For |A(S)| = 4, the proof establishes sufficient flow capacity with zero or one bad edge, and treats two bad edges as a perfect matching whose incident higher-edge values are ε_F-fractional.In the two-bad-edge case, the capacity bound follows using ε_B ≥ 2ε_1/2 and α ≥ 2ε_η.Source: §6 · p. 67

7 Reduction and payment

Section 7 develops reduction events and an increase vector, using bounds on expected increases to establish the main payment theorem. It bounds expected contributions in several cases, including good top edges under stated parameter conditions, degree-cut parents (0.99994βp), and interior atoms of polygon cuts (0.85βp).

7 Reduction and payment

  • Happy events are subsampled to probability p, defining reduction indicators for bottom edges and good top-edge bundles, with shared indicators for certain neighboring bundles.For the specified case-3 neighboring half-edge bundles, the indicators use the same measure-p subset of their intersecting events.Source: §7 · p. 68
  • The increase-vector bound gives E[IS] ≤ 0.99994βp for bottom edge bundles and bounds expected increase for any good top edge bundle.The section uses Theorem 7.1 to establish the good-edge expected-payment bound in Theorem 4.33.Source: §7 · pp. 69–70
  • For an LP solution, Theorem 4.33 provides a good-edge set and payment vector with edgewise lower bounds, a negative expected payment for good edges, and safeguards for specified polygon and odd cuts.The good-edge set covers at least 3/4 of the LP mass across non-root degree cuts; the theorem also gives a polygon-cut inequality when the cut is not left happy.Source: §7 · pp. 69–70
  • Theorem 4.33 also requires that an unhappy polygon cut obey a payment inequality for qualifying edge sets, and that non-polygon cuts have nonnegative payment when their sampled cut is odd.The polygon-cut statement includes the condition x(F) ≥ 1 − εη/2; the odd-cut guarantee applies when p(S) is not a polygon cut.Source: §7 · pp. 69–70

7.1 Increase for Good Top Edges

  • Under the stated epsilon conditions, subsection 7.1 develops the increase bound for good top edges through Lemmas 7.2 and 7.3.Lemma 7.3 is identified as a technical lemma used to prove the top-edge increase result.Source: §7.1 · pp. 71–72

7.2 Increase for Bottom Edges

  • For a degree-cut parent, the expected bottom-edge contribution is at most 0.99994βp.This is the first of three cases considered, with the other cases involving polygon-cut parents.Source: §7.2 · p. 78

7.2.1 Case 1: ˆS is a degree cut

  • For a degree-cut parent, the proof treats bad half edges, sufficient mass on 2-1-1 good edges, and otherwise simultaneous reduction of two 2-2-2 good top half-edge bundles.In the 2-1-1 case, the edge set has x(D) ≥ 1/2 − ǫ1/2 − ǫη; in the remaining case, the chosen 2-2-2 bundles reduce simultaneously when happy.Source: §7.2.1 · p. 79

7.2.2 Case 2: S and its parent ˆS are both polygon cuts

  • For a polygon-cut parent, endpoint and interior atoms are bounded separately; the interior-atom bound is 0.85βp.The endpoint case is handled by Lemma 7.9 and the interior case by Lemma 7.11.Source: §7.2.2 · pp. 80, 82

A Proofs from Section 5

The appendix proves probabilistic guarantees for edge bundles to be 2-1-1 happy or good, and for a pair of bundles to be 2-2-2 happy. Its arguments use conditioning, marginal bounds, and log-concavity to establish the stated guarantees.

Lemma 5.21

  • For a top edge bundle with xe ≤ 1/2 − ε1/2 and ε1/2 ≤ 0.001, the bundle is 2-1-1 happy with probability at least 0.005ε^2.Conditioning and bounds on the expected edge counts lead to a positive probability of the required count pattern.Source: A Proofs from Section 5 · pp. 86–87

Lemma 5.22

  • For a top edge bundle with xe ≥ 1/2 + ε1/2 and ε1/2 ≤ 0.001, the bundle is 2-1-1 happy with respect to u with probability at least 0.006ε^2.The proof bounds the probabilities of several combinations of edge counts under a conditioned measure, then applies Corollary 5.5.Source: A Proofs from Section 5 · p. 87

Lemma A.1

  • Under Lemma A.1’s assumptions, a good half top edge bundle is 2-1-1 good.The proof derives Pν[AT + BT + VT = 3] ≥ 0.2ε1/2 using log-concavity, and bounds Pν[AT + VT ≤ 2] below by 4.8ε1/2.Source: A Proofs from Section 5 · pp. 88–89

Lemma 5.23

  • For two good half top edge bundles satisfying the stated degree-partition conditions, at least one is 2-1-1 happy with probability at least 0.005ε².The proof obtains a probability lower bound of 0.01 for a related edge-count event and applies Lemma A.1.Source: A Proofs from Section 5 · p. 89

Lemma 5.24

  • Under the stated conditioning in Lemma 5.24, Pν[XT = 1|XT + YT = 2] ≥ 0.119.The proof uses the event XT = YT = 1 to correct the parity of A and B by choosing from eA or eB.Source: A Proofs from Section 5 · p. 90

Lemma 5.27

  • A pair of good top half edge bundles is 2-2-2 happy with probability greater than 0.01 under the stated small-ε and goodness conditions.The proof conditions on an event of probability at least 1/5 and bounds the relevant tree-edge counts after conditioning.Source: A Proofs from Section 5 · pp. 91–93

Related papers

Loading 2007.01409v6…