Approximate multi-matroid intersection via iterative refinement
METADATA ONLY
Loading...
Author / Producer
Date
2020-09
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
Abstract
We introduce a new iterative rounding technique to round a point in a matroid polytope subject to further matroid constraints. This technique returns an independent set in one matroid with limited violations of the constraints of the other matroids. In addition to the classical steps of iterative relaxation approaches, we iterativelyrefineinvolved matroid constraints. This leads to more restrictive constraint systems whose structure can be exploited to prove the existence of constraints that can be dropped. Hence, throughout the iterations, we both tighten constraints and later relax them by dropping constraints under certain conditions. Due to the refinement step, we can deal with considerably more general constraint classes than existing iterative relaxation and rounding methods, which typically involve a single matroid polytope with additional simple cardinality constraints that do not overlap too much. We show that our rounding method, combined with an application of a matroid intersection algorithm, yields the first 2-approximation for finding a maximum-weight common independent set in 3 matroids. Moreover, our 2-approximation is LP-based and settles the integrality gap for the natural relaxation of the problem. Prior to our work, no upper bound better than 3 was known for the integrality gap, which followed from the greedy algorithm. We also discuss various other applications of our techniques, including an extension that allows us to handle a mixture of matroid and knapsack constraints. (© 2020 Springer).
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
193
Pages / Article No.
397 - 418
Publisher
Springer
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Organisational unit
09487 - Zenklusen, Rico / Zenklusen, Rico
Notes
Funding
184622 - Toward Stronger Approximation Algorithms for Fundamental Network Design and Optimization Problems (SNF)
165866 - New Approaches to Constrained Submodular Maximization (SNF)
165866 - New Approaches to Constrained Submodular Maximization (SNF)