Iterative packing for demand and hypergraph matching

DOI10.1007/978-3-642-20807-2_28MaRDI QIDQ3009775zbMATH OpenOpenAlexFDO

Authors Ojas Parekh

Publication date 24 June 2011

Published in Integer Programming and Combinatoral Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1604.00310

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Matching models (91B68)

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.

Recommendations

• Generalized hypergraph matching via iterated packing and local ratio
• Further approximations for demand matching: matroid constraints and minor-closed graphs
• Algorithms to approximate column-sparse packing problems
• New developments in iterated rounding (invited talk)
• Iterative partial rounding for vertex cover with hard capacities

Cites work

• scientific article; zbMATH DE number 6297805 (Why is no real title available?)
• A factor 2 approximation algorithm for the generalized Steiner network problem
• Approximability of Sparse Integer Programs
• Approximability of sparse integer programs
• Approximating disjoint-path problems using packing integer programs
• Approximating minimum bounded degree spanning trees to within one of optimal
• Distributed Fractional Packing and Maximum Weighted b-Matching via Tail-Recursive Duality
• Mathematical Foundations of Computer Science 2005
• Multicommodity demand flow in a tree and packing integer programs
• On k-column sparse packing programs
• On the complexity of approximating \(k\)-set packing
• On the fractional matching polytope of a hypergraph
• Randomized metarounding
• Scheduling Split Intervals
• The Demand-Matching Problem
• Unsplittable Flow in Paths and Trees and Column-Restricted Packing Integer Programs

Cited in

(12)

• Constant factor approximation for the weighted partial degree bounded edge packing problem
• Constant factor approximation for the weighted partial degree bounded edge packing problem
• scientific article; zbMATH DE number 1757945 (Why is no real title available?)
• Iterative methods in combinatorial optimization
• Further approximations for demand matching: matroid constraints and minor-closed graphs
• Efficient implementation of Carathéodory's theorem for the single machine scheduling polytope
• Stochastic packing integer programs with few queries
• Generalized hypergraph matching via iterated packing and local ratio
• Integrality gaps for colorful matchings
• New developments in iterated rounding (invited talk)
• Multicommodity flow in trees: packing via covering and iterated relaxation
• The Demand-Matching Problem

This page was built for publication: Iterative packing for demand and hypergraph matching

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3009775)