Iterative Packing for Demand and Hypergraph Matching
Author:
Preprint
Abstract
Iterative rounding has enjoyed tremendous success in elegantly resolving open questions regarding the approximability of problems dominated by covering constraints. Although iterative rounding methods have been applied to packing problems, no single method has emerged that matches the effectiveness and simplicity afforded by the covering case. We offer a simple iterative packing technique that retains features of Jain's seminal approach, including the property that the magnitude of the fractional value of the element rounded during each iteration has a direct impact on the approximation guarantee. We apply iterative packing to generalized matching problems including demand matching and $k$-column-sparse column-restricted packing ($k$-CS-PIP) and obtain approximation algorithms that essentially settle the integrality gap for these problems. We present a simple deterministic $2k$-approximation for $k$-CS-PIP, where an $8k$-approximation was the best deterministic algorithm previously known. The integrality gap in this case is at least $2(k-1+1/k)$. We also give a deterministic $3$-approximation for a generalization of demand matching, settling its natural integrality gap.
Keywords
All Related Versions
- Version 1, 2016-04-01, ArXiv
- Published version: Lecture Notes in Computer Science, 349.
This publication has 11 references indexed in Scilit:
- Approximability of Sparse Integer ProgramsAlgorithmica, 2010
- On Linear and Semidefinite Programming Relaxations for Hypergraph Matching2010
- The Demand-Matching ProblemMathematics of Operations Research, 2007
- Approximating minimum bounded degree spanning trees to within one of optimal2007
- On the complexity of approximating k-set packingcomputational complexity, 2006
- Scheduling Split IntervalsSIAM Journal on Computing, 2006
- Approximating disjoint-path problems using packing integer programsMathematical Programming, 2004
- Randomized metaroundingRandom Structures & Algorithms, 2002
- A Factor 2 Approximation Algorithm for the Generalized Steiner Network ProblemCombinatorica, 2001
- On the fractional matching polytope of a hypergraphCombinatorica, 1993