Document Open Access Logo

Oblivious Rounding and the Integrality Gap

Authors Uriel Feige, Michal Feldman, Inbal Talgam-Cohen

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2016.8.pdf
  • Filesize: 0.53 MB
  • 23 pages

Document Identifiers

Author Details

Uriel Feige
Michal Feldman
Inbal Talgam-Cohen

Cite As Get BibTex

Uriel Feige, Michal Feldman, and Inbal Talgam-Cohen. Oblivious Rounding and the Integrality Gap. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 8:1-8:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2016.8

Abstract

The following paradigm is often used for handling NP-hard combinatorial optimization problems. One first formulates the problem as an integer program, then one relaxes it to a linear program (LP, or more generally, a convex program), then one solves the LP relaxation in polynomial time, and finally one rounds the optimal LP solution, obtaining a feasible solution to the original problem. Many of the commonly used rounding schemes (such as randomized rounding, threshold rounding and others) are "oblivious" in the sense that the rounding is performed based on the LP solution alone, disregarding the objective function. The goal of our work is to better understand in which cases oblivious rounding suffices in order to obtain approximation ratios that match the integrality gap of the underlying LP. Our study is information theoretic - the rounding is restricted to be oblivious but not restricted to run in polynomial time. In this information theoretic setting we characterize the approximation ratio achievable by oblivious rounding. It turns out to equal the integrality gap of the underlying LP on a problem that is the closure of the original combinatorial optimization problem. We apply our findings to the study of the approximation ratios obtainable by oblivious rounding for the maximum welfare problem, showing that when valuation functions are submodular oblivious rounding can match the integrality gap of the configuration LP (though we do not know what this integrality gap is), but when valuation functions are gross substitutes oblivious rounding cannot match the integrality gap (which is 1).

Subject Classification

Keywords
  • Welfare-maximization

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Ashwinkumar Badanidiyuru, Shahar Dobzinski, Hu Fu, Robert Kleinberg, Noam Nisan, and Tim Roughgarden. Sketching valuation functions. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1025-1035, 2012. Google Scholar
  2. Sushil Bikhchandani and John W. Mamer. Competitive equilibrium in an exchange economy with indivisibilities. Journal of Economic Theory, 74(2):385-413, 1997. Google Scholar
  3. Robert Carr and Santosh Vempala. Randomized metarounding. Random Structures and Algorithms, 20(3):343-352, 2002. Google Scholar
  4. Deeparnab Chakrabarty and Gagan Goel. On the approximability of budgeted allocations and improved lower bounds for submodular welfare maximization and GAP. SIAM J. Comput., 39(6):2189-2211, 2010. Google Scholar
  5. Nan Du, Yingyu Liang, Maria-Florina Balcan, and Le Song. Learning time-varying coverage functions. In Proceedings of the 27th Neural Information Processing Systems Conference, pages 3374-3382, 2014. Google Scholar
  6. Shaddin Dughmi, Tim Roughgarden, and Qiqi Yan. From convex optimization to randomized mechanisms: Toward optimal combinatorial auctions. In Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, pages 149-158, 2011. Google Scholar
  7. Paul Dütting, Thomas Kesselheim, and Éva Tardos. Algorithms as mechanisms: The price of anarchy of relax-and-round. In Proceedings of the 16th ACM Conference on Economics and Computation, pages 187-201, 2015. Google Scholar
  8. Uriel Feige. On maximizing welfare when utility functions are subadditive. SIAM J. Comput., 39(1):122-142, 2009. Google Scholar
  9. Uriel Feige and Shlomo Jozeph. Oblivious algorithms for the maximum directed cut problem. Algorithmica, 71(2):409-428, 2015. Google Scholar
  10. Uriel Feige and Jan Vondrák. The submodular welfare problem with demand queries. Theory of Computing, 6(1):247-290, 2010. Google Scholar
  11. Michel X. Goemans and David P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM, 42(6):1115-1145, 1995. Google Scholar
  12. Avinatan Hassidim and Yaron Singer. Submodular optimization under noise. Manuscript, 2016. Google Scholar
  13. Dorit S. Hochbaum. Approximation algorithms for the set covering and vertex cover problems. SIAM Journal on Computing, 11:555-–556, 1982. Google Scholar
  14. Alexander S. Kelso and Vincent P. Crawford. Job matching, coalition formation, and gross substitutes. Econometrica, 50(6):1483-1504, 1982. Google Scholar
  15. Ron Lavi and Chaitanya Swamy. Truthful and near-optimal mechanism design via linear programming. Journal of the ACM, 58(6), 2011. Article 25. Google Scholar
  16. Shi Li. A 1.488 approximation algorithm for the uncapacitated facility location problem. Information and Computation, 222:45-58, 2013. Google Scholar
  17. Kazuo Murota. Valuated matroid intersection I: Optimality criteria. SIAM J. Discrete Math., 9(4):545-561, 1996. Google Scholar
  18. Kazuo Murota. Valuated matroid intersection II: Algorithms. SIAM J. Discrete Math., 9(4):562-576, 1996. Google Scholar
  19. Kazuo Murota. Discrete Convex Analysis. Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics, 2003. Google Scholar
  20. Noam Nisan and Ilya Segal. The communication requirements of efficient allocations and supporting prices. Journal of Economic Theory, 129:192-224, 2006. Google Scholar
  21. Renato Paes Leme. Gross substitutability: An algorithmic survey. Working paper, 2014. Google Scholar
  22. Prabhakar Raghavan and Clark D. Thompson. Randomized rounding: A technique for provably good algorithms and algorithmic proofs. Combinatorica, 7(4):365-374, 1987. Google Scholar
  23. Prasad Raghavendra and David Steurer. How to round any CSP. In Proceedings of the 50th Symposium on Foundations of Computer Science, pages 586-594, 2009. Google Scholar
  24. Tim Roughgarden, Inbal Talgam-Cohen, and Jan Vondràk. When are welfare guarantees robust? Working paper, 2016. Google Scholar
  25. Aravind Srinivasan. Budgeted allocations in the full-information setting. In Proceedings of the 11th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, pages 247-253, 2008. Google Scholar
  26. John von Neumann. Zur theorie der gesellschaftsspiele. Math. Annalen., 100:295-320, 1928. Google Scholar
  27. Neal E. Young. Randomized rounding without solving the linear program. In Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 170-178, 1995. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact