TY - GEN
T1 - Multi-budgeted matchings and matroid intersection via dependent rounding
AU - Chekuri, Chandra
AU - Vondrák, Jan
AU - Zenklusen, Rico
PY - 2011
Y1 - 2011
N2 - Motivated by multi-budgeted optimization and other applications, we consider the problem of randomly rounding a fractional solution X in the (non-bipartite graph) matching and matroid intersection polytopes. We show that for any fixed δ > 0, a given point X can be rounded to a random solution R such that E[1R] = (1 - δ)x and any linear function of x satisfies dimension-free Chernoff-Hoeffding concentration bounds (the bounds depend on δ and the expectation μ). We build on and adapt the swap rounding scheme in our recent work [9] to achieve this result. Our main contribution is a non-trivial martingale based analysis framework to prove the desired concentration bounds. In this paper we describe two applications. We give a randomized PTAS for matroid intersection and matchings with any fixed number of budget constraints. We also give a deterministic PTAS for the case of matchings. The concentration bounds also yield related results when the number of budget constraints is not fixed. As a second application we obtain an algorithm to compute in polynomial time an ε-approximate Pareto-optimal set for the multi-objective variants of these problems, when the number of objectives is a fixed constant. We rely on a result of Papadimitriou and Yannakakis [26].
AB - Motivated by multi-budgeted optimization and other applications, we consider the problem of randomly rounding a fractional solution X in the (non-bipartite graph) matching and matroid intersection polytopes. We show that for any fixed δ > 0, a given point X can be rounded to a random solution R such that E[1R] = (1 - δ)x and any linear function of x satisfies dimension-free Chernoff-Hoeffding concentration bounds (the bounds depend on δ and the expectation μ). We build on and adapt the swap rounding scheme in our recent work [9] to achieve this result. Our main contribution is a non-trivial martingale based analysis framework to prove the desired concentration bounds. In this paper we describe two applications. We give a randomized PTAS for matroid intersection and matchings with any fixed number of budget constraints. We also give a deterministic PTAS for the case of matchings. The concentration bounds also yield related results when the number of budget constraints is not fixed. As a second application we obtain an algorithm to compute in polynomial time an ε-approximate Pareto-optimal set for the multi-objective variants of these problems, when the number of objectives is a fixed constant. We rely on a result of Papadimitriou and Yannakakis [26].
UR - http://www.scopus.com/inward/record.url?scp=79955731850&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=79955731850&partnerID=8YFLogxK
U2 - 10.1137/1.9781611973082.82
DO - 10.1137/1.9781611973082.82
M3 - Conference contribution
AN - SCOPUS:79955731850
SN - 9780898719932
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 1080
EP - 1097
BT - Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011
PB - Association for Computing Machinery
ER -