Source-linked AI summary
Improved Integrality Gap for Multicommodity Flow on Trees
Elfarouk Harb
TL;DR
The paper studies lower bounds on the integrality gap, defined as the infimum ratio of integer optimum to LP optimum. It uses scaled-copy rounding and recursive coloring to improve an intermediate 4/11 bound to 2/5.
Problem
The paper studies lower bounds on the integrality gap, defined as the infimum ratio of integer optimum to LP optimum.
Source: §1 · p. 1Method
The proof scales capacities and makes four copies of each request, then recursively colors selected copies by removing and restoring end stars.
Source: The idea of the proof · p. 3Results
2W/5 is obtained with ten colors, improving on the intermediate 4/11 bound.
Source: §1 · p. 1, The idea of the proof · p. 3Takeaways & Limitations
The refinement reduces the coloring from eleven colors to ten to obtain the 2/5 lower bound.
Source: The idea of the proof · p. 3The stated coloring guarantee has bins containing at most six paths and at most ue bins at a leaf with incident edge e.
Source: §3 · p. 5
Abstract
from arXiv · showhide
We improve the best known lower bound on the integrality gap for weighted unit-demand multicommodity flow on trees from $1/4$ to $2/5$, improving on the long-standing bound of Chekuri, Mydlarz, and Shepherd~\cite{CMS}. We give the proof in two stages. First, a surprisingly simple packing lemma and an inductive coloring argument give an intermediate bound of $4/11$. We then refine the argument to obtain $2/5$.
1 Introduction and main result
The paper proves a stronger lower bound on the integrality gap for weighted multicommodity flow on trees. Its proof first obtains a 4/11 bound, then refines the coloring argument to reach 2/5.
1 Introduction and main result
- Before this work, the best known integrality-gap bounds for arbitrary weights and arbitrary capacities were a lower bound of 1/4 and an upper bound of 2/3, respectively.Source: §1 · p. 2
- Four copies of each request and capacities scaled by four yield selected copies of weight at least 4W, which are partitioned into eleven feasible classes with no duplicate original request per class.The copy restriction ensures a class's weight agrees with the corresponding weight in the original instance.Source: The idea of the proof · p. 3
- The first stage gives a 4/11 bound: the heaviest color class has weight at least 4W/11; Section 2 explains how to enforce the conditions and gives the full reduction.Source: §1 · p. 1, The idea of the proof · p. 3
- The eleven-coloring construction handles a general tree by recursively removing a star, coloring the smaller tree, then restoring paths while retaining information about earlier bins.The binning and contraction coloring argument is introduced as the elementary intermediate proof.Source: §1 · p. 2, The idea of the proof · p. 3
- 2/5 is the final integrality-gap lower bound, improving on the previously known 1/4 lower bound for arbitrary weights and capacities.The paper also reports that the prior upper bound was 2/3.Source: §1 · p. 2, The idea of the proof · p. 3
2 Reduction to a coloring problem
The reduction converts a fractional solution of value W into an eleven-coloring problem whose color classes yield a feasible original-instance subset of weight at least 4W/11.
2 Reduction to a coloring problem
- Adding two capacity-one private leaf edges per request preserves feasible fractional solutions and their value while encoding the one-copy-per-class restriction.All copies of a request share the same private edges; each extended request still uses the original edges and retains its weight.Source: §2 · p. 4
- Four labeled copies of each extended request, with every enlarged-tree edge capacity scaled to 4u_e, yield fractional objective 4W; Theorem 2.1 selects copies of total weight at least 4W, with edge load at most 4u_e + 2.Source: §2 · p. 4
- Theorem 2.2 colors paths with edge load at most 4u_e + 2 using eleven colors, with at most u_e paths of each color on each edge.The paths are labeled, so repeated paths are treated as distinct objects.Source: §2 · pp. 3–4
- At least one of eleven color classes yields a feasible original-instance subset of weight at least 4W/11.The private capacity-one edges ensure each class contains at most one copy of any original request, so replacing copies preserves weight.Source: §2 · p. 4
3 The coloring argument
The coloring argument proves a stronger bin-respecting eleven-coloring theorem by induction on internal vertices, then uses it to color paths under the load bound 4u_e + 2.
3 The coloring argument
- Six-path bins and at most u bins per leaf imply at most u paths of any color use a leaf edge of capacity u.At most 4u + 2 paths end at a leaf, and 4u + 2 ≤ 6u for u ≥ 1, so consecutive groups of six require at most u bins.Source: §3 · p. 5
- On a tree with positive integer edge capacities, if prescribed bins contain at most six paths, each leaf has at most u_e bins, and each internal edge e is used by at most 4u_e + 2 paths, an eleven-coloring makes paths distinct within each bin.Source: §3 · p. 5
- For a star or single edge, coloring paths greedily avoids at most ten colors from the two endpoint bins, leaving one of eleven colors available.Pairwise-distinct colors within bins then satisfy the edge capacities.Source: §3 · pp. 5–6
- For larger trees, the induction contracts an attached star, removes local paths, and turns crossing paths into paths incident to the new leaf.Crossing blocks are packed into at most u_vw bins of size at most six, using the load bound on vw; Lemma A.1 guarantees this packing.Source: §3 · p. 6
- After recursively coloring the smaller tree, restoring local paths greedily preserves distinct colors within each bin and the capacity bound on every edge.Theorem 3.1 immediately implies the eleven-coloring theorem for paths with load at most 4u_e + 2.Source: §3 · pp. 5, 7
4 The algorithm
The algorithm implements the rounding-and-coloring proof in polynomial time, choosing the maximum-weight color class and mapping its copies back to original requests.
4 The algorithm
- The algorithm solves the LP, adds private leaves, makes four copies, scales capacities by four, rounds, colors, and returns a maximum-weight class as original requests.It contracts attached stars, greedily colors the remaining star or single edge, then restores contractions while coloring local paths.Source: §4 · p. 7
- All operations take polynomial time and space, including contractions, path and bin tracking, and the packing-lemma merges.Only nonempty bins are stored, so representation size does not grow with numerical capacity values.Source: §4 · p. 7
- The enlarged tree adds two leaves per request, and the copied instance uses only four copies per request.Each contraction reduces the number of internal vertices.Source: §4 · p. 7
5 Saving the eleventh color
The section obtains a ten-color inductive coloring by completing local paths around an attached star, using a bin-moving reduction for the exceptional case. The recursion terminates and runs in polynomial time.
5 Saving the eleventh color
- With eleven colors, greedy coloring always leaves a color available, but with ten it may get stuck because two bins can exclude all ten colors.The approach therefore keeps crossing-path colors fixed and chooses local-path colors together, using an edge-coloring theorem.Source: §5 · p. 7
- Lemma 5.1 completes local paths with ten colors when each bin has at most four crossing paths, or when at most six crossing paths have distinct colors.In either case, the completed coloring keeps the prescribed crossing colors and makes paths within each bin distinct.Source: §5 · pp. 7–8
- Ten colors suffice to give distinct colors to paths in each prescribed bin while keeping each edge's per-color load within its capacity.The theorem applies under the assumptions of Theorem 3.1.Source: §5 · p. 8
- If each bin at the star's leaves has at most four crossing paths, contracting the star groups them into at most u bins of size at most six for recursive coloring.On restoration, Lemma 5.1(a) colors the local paths without changing crossing colors.Source: §5 · p. 8
- When u = 1, contraction also works with bins containing five or six crossing paths, since all crossing paths fit in one bin and receive distinct colors.Lemma 5.1(b) then completes the local paths.Source: §5 · p. 8
- For u ≥ 2 and a bin with at least five crossing paths, moving that bin's endpoints to a new leaf removes at least five paths from vw and adds at most one.The construction lowers vw's capacity by one and gives the new edge capacity one; if av had capacity one, av and leaf a are deleted.Source: §5 · pp. 8–9
- After recursive coloring, restoring the moved paths adds at most one path of each color to av and vw, preserving both capacity bounds; the recursion terminates by decreasing a nonnegative path-length measure.The resulting algorithm runs in polynomial time.Source: §5 · pp. 9–10
A Packing lemma
The packing lemma bounds the number of bins needed for indivisible items of size at most six. Its proof repeatedly merges compatible bins and uses a lower bound on the terminal bin count.
A Packing lemma
- Items of positive integer size at most six and total size at most 4u + 2 fit into at most u bins of size at most six without splitting.Here u is an integer at least one.Source: A Packing lemma · p. 10
- Repeatedly merging any two bins whose combined size is at most six preserves the size limit and terminates because each merge reduces the bin count.The proof starts with one bin per item.Source: A Packing lemma · p. 10
- At termination, q bins have total size L ≥ 4q − 1; if q > u, this contradicts the assumed bound L ≤ 4u + 2.Thus the terminal number of bins is at most u.Source: A Packing lemma · p. 10
B Specialization of the edge-coloring theorem
The proof of Lemma 5.1 represents bins and paths as a graph to apply an edge-coloring theorem. A separate graph construction yields a polynomial-time coloring extension algorithm.
B Specialization of the edge-coloring theorem
- Lemma 5.1 specializes Edwards et al. [Edwards et al., 2018, Theorem 9] by representing bins as vertices and local paths as edges.Crossing paths are represented by precolored edges to separate leaves in case (a), or to one common vertex in case (b).Source: B Specialization of the edge-coloring… · p. 10
- In both cases, the graph has maximum degree at most six, allowing the theorem to complete the coloring while respecting the crossing-path colors.In case (b), permuting colors matches the colors at the common vertex to the distinct prescribed colors.Source: B Specialization of the edge-coloring… · p. 10
- The coloring extension runs in polynomial time by converting the multigraph's edge-coloring problem into vertex coloring of a graph with maximum degree at most ten.Chlebík and Chlebíková [Chlebík and Chlebíková, 2006, Theorem 3] provide the extension algorithm.Source: B Specialization of the edge-coloring… · p. 11