arXiv preprint ·
A $59/33$ Cut-LP Guarantee for Matching Augmentation
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
The Matching Augmentation Problem (MAP) asks for a minimum-cardinality set of unit-cost edges that, together with a zero-cost matching, forms a 2-edge-connected spanning multigraph. We study the standard cut relaxation. Bamas, Drygala, and Svensson proposed a particularly simple LP-guided algorithm: compute an extreme optimum, run a depth-first search that prioritizes large LP coordinates, and augment the resulting DFS tree optimally. We give a new structural analysis of the Bamas--Drygala--Svensson LP-guided DFS algorithm. The analysis combines an exact primal--dual identity for the residual uplink problem with a rank bound that measures fractional support relative to the unit-valued skeleton. The result is that for every root and every deterministic tie-breaking order consistent with the LP priorities, the algorithm returns a solution of cost at most $\frac{59}{33}c(x^*)-\frac{25}{33}=\left(2-\frac7{33}\right)c(x^*)-\frac{25}{33}\approx1.788c(x^*)-0.758$, where $x^*$ is an optimum of the cut LP. Consequently, the integrality gap of the relaxation is at most $59/33\approx1.788$. No new algorithmic step is required; the improvement is analytical. The exact packing certificate for the residual uplink problem yields a cost identity with a packing-slack term, while a rank theorem bounds fractional support relative to the unit-valued skeleton. A regional classification accounts for the non-tree edges, and a two-cut identity handles self-holes. As a direct corollary, the same $59/33\approx1.788$ bound holds for Forest Augmentation in the minimum-value regime. The proof is self-contained apart from one theorem on the dimension of minimum-cut vectors.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Linear-Query Deterministic Approximation for Non-monotone Submodular Maximization under a Knapsack Constraint
Boyer-Moore Variants for Indeterminate String Matching and Experimental Evaluation
Improved Algorithms for the Remote Point Problem
$c$-Packedness versus $λ$-Low-Density in Geometric Graphs: Theory and Practice
Exponential Quantum Advantage in Testing Fourier Dimensionality
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.