research-article

How well can primal-dual and local-ratio algorithms perform?

Authors:

Avner MagenAuthors Info & Claims

ACM Transactions on Algorithms (TALG), Volume 7, Issue 3

Article No.: 29, Pages 1 - 26

https://doi.org/10.1145/1978782.1978784

Published: 15 July 2011 Publication History

Abstract

We define an algorithmic paradigm, the stack model, that captures many primal-dual and local-ratio algorithms for approximating covering and packing problems. The stack model is defined syntactically and without any complexity limitations and hence our approximation bounds are independent of the P versus NP question. Using the stack model, we bound the performance of a broad class of primal-dual and local-ratio algorithms and supply a (log n+1)/2 inapproximability result for set cover, a 4/3 inapproximability for min Steiner tree, and a 0.913 inapproximability for interval scheduling on two machines.

References

[1]

Adamy, U., Erlebach, T., Mitsche, D., Schurr, I., Speckmann, B., and Welzl, E. 2004. Off-Line admission control for advance reservations in star networks. In Proceedings of the Workshop on Approximation and Online Algorithms (WAOA'04). 211--224.

Digital Library

[2]

Agrawal, A., Klein, P., and Ravi, R. 1995. When trees collide: An approximation algorithm for the generalized steiner problem on networks. SIAM J. Comput. 24, 440--465.

Digital Library

[3]

Akcoglu, K., Aspnes, J., Dasgupta, B., and Kao, M.-Y. 2000. Opportunity cost algorithms for combinatorial auctions. CoRR cs.CE/0010031, 143--167.

[4]

Alekhnovich, M., Borodin, A., Buresh-Oppenheim, J., Impagliazzo, R., Magen, A., and Pitassi, T. 2005. Toward a model for backtracking and dynamic programming. In Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC'05). IEEE Computer Society, Los Alamitos, CA.

Digital Library

[5]

Amzallag, D., Bar-Yehuda, R., Raz, D., and Scalosub, G. 2008. Cell selection in 4g cellular networks. In Proceedings of the 27th Annual Joint Conference of the IEEE Computer and Communications Societies (InfoCom'08). 700--708.

[6]

Angelopoulos, S. and Borodin, A. 2004. On the power of priority algorithms for facility location and set cover. Algorithmica 40, 4, 271--291.

Digital Library

[7]

Arkin, E. M. and Silverberg, E. L. 1987. Scheduling jobs with fixed start and end times. Discr. Appl. Math. 18, 1--8.

Digital Library

[8]

Arora, S., Bollobas, B., and Lovasz, L. 2002. Proving integrality gaps without knowing the linear program. In Proceedings of the 43rd Annual IEEE Conference on Foundations of Computer Science. IEEE Computer Society, Los Alamitos, CA, 313--322.

Digital Library

[9]

Arora, S., Bollobas, B., Lovasz, L., and Tourlakis, I. 2006. Proving integrality gaps without knowing the linear program. Theory Comput. 2, 2, 19--51.

[10]

Bafna, V., Berman, P., and Fujito, T. 1995. Constant ratio approximations of the weighted feedback vertex set problem for undirected graphs. In Proceedings of the International Symposium on Algorithms and Computation (ISAAC'95). 142--151.

Digital Library

[11]

Bar-Noy, A., Bar-Yehuda, R., Freund, A., Naor, J., and Schieber, B. 2001. A unified approach to approximating resource allocation and scheduling. J. ACM 48, 5, 1069--1090.

Digital Library

[12]

Bar-Noy, A., Guha, S., Katz, Y., Naor, J., Schieber, B., and Shachnai, H. 2009. Throughput maximization of real-time scheduling with batching. ACM Trans. Algor. 5, 2, 18:1--18:17.

Digital Library

[13]

Bar-Yehuda, R., Beder, M., Cohen, Y., and Rawitz, D. 2009. Resource allocation in bounded degree trees. Algorithmica 54, 1, 89--106.

Digital Library

[14]

Bar-Yehuda, R., Bendel, A., Freund, A., and Rawitz, D. 2004. Local ratio: A unified framework for approximation algorithms: In memoriam Shimon Even 1935--2004. ACM Comput. Surv. 36, 422--463.

Digital Library

[15]

Bar-Yehuda, R. and Even, S. 1981. A linear time approximation algorithm for the weighted vertex cover problem. J. Algor. 2, 198--203.

[16]

Bar-Yehuda, R., Halldorsson, M. M., Naor, J., Shachnai, H., and Shapira, I. 2002. Scheduling split intervals. In Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics, Philadelphia, PA, 732--741.

Digital Library

[17]

Bar-Yehuda, R. and Rawitz, D. 2005. On the equivalence between the primal-dual schema and the local ratio technique. SIAM J. Discr. Math. 19, 3, 762--797.

Digital Library

[18]

Bar-Yehuda, R. and Rawitz, D. 2006. Using fractional primal-dual to schedule split intervals with demands. Discr. Optimiz. 3, 4, 275--287.

Digital Library

[19]

Becker, A. and Geiger, D. 1994. Approximation algorithms for the loop cutset problem. In Proceedings of the 10^th Conference on Uncertainty in Artificial Intelligence. 60--68.

[20]

Berman, P. and Dasgupta, B. 2002. A simple approximation algorithm for nonoverlapping local alignments (weighted independent sets of axis parallel rectangles). Biocomput. 1, 129--138.

[21]

Berman, P. and Gupta, B. D. 2000. Improvements in throughput maximization for real-time scheduling. In Proceedings of the ACM Symposium on Theory of Computing (STOC'00). ACM, New York.

Digital Library

[22]

Bertsimas, D. and Teo, C.-P. 1998. From valid inequalities to heuristics: A unified view of primal-dual approximation algorithms in covering problems. Oper. Res. 46, 4, 503--514.

Digital Library

[23]

Borodin, A., Nielsen, M. N., and Rackoff, C. 2003. (Incremental) priority algorithms. Algorithmica 37, 4, 295--326.

Digital Library

[24]

Buresh-Oppenheim, J., Davis, S., and Impagliazzo, R. 2010. A stronger model of dynamic programming algorithms. Algorithmica (To appear).

Digital Library

[25]

Byrka, J., Grandoni, F., Rothvoss, T., and Sanita, L. 2010. An improved lp-based approximation for steiner tree. In Proceedings of the ACM Symposium on Theory of Computing (STOC'10). ACM, New York, 583--592.

Digital Library

[26]

Calinescu, G., Chakrabarti, A., Karloff, H., and Rabani, Y. 2002. Improved approximation algorithms for resource allocation. In Proceedings of the 9th International Integer Programming and Combinatorial Optimization Conference (IPCO'02). Lecture Notes in Computer Science, vol. 2337. Springer, 40--414.

Digital Library

[27]

Chakrabarty, D., Devanur, N. R., and Vazirani, V. V. 2008. New geometry-inspired relaxations and algorithms for the metric steiner tree problem. In Proceedings of the 13th Integer Programming and Combinatorial Optimization Conference (IPCO'08). Lecture Notes in Computer Science, vol. 5035. Springer, 344--358.

Digital Library

[28]

Chakrabarty, D., Konemann, J., and Pritchard, D. 2010. Hypergraphic lp relaxations for steiner trees. In Proceedings of the Integer Programming and Combinatorial Optimization Conference (IPCO'10). Springer, 383--396.

Digital Library

[29]

Charikar, M., Makarychev, K., and Makarychev, Y. 2009. Integrality gaps for Sherali-Adams relaxations. In Proceedings of the ACM Symposium on Theory of Computing (STOC'09). ACM Press, New York.

Digital Library

[30]

Chlebik, M. and Chlebikova, J. 2008. The steiner tree problem on graphs: Inapproximability results. Theor. Comput. Sci. 406, 3, 207--214.

Digital Library

[31]

Chudak, F. A., Goemans, M. X., Hochbaum, D. S., and Williamson, D. P. 1998. A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs. Oper. Res. Lett. 22, 111--118.

Digital Library

[32]

Chvatal, V. 1980. Hard knapsack problems. Oper. Res. 28, 6, 1402--1441.

Digital Library

[33]

Davis, S. and Impagliazzo, R. 2009. Models of greedy algorithms for graph problems. Algorithmica 54, 3, 269--317.

Digital Library

[34]

Dechter, A. and Dechter, R. 1989. On the greedy solution of ordering problems. ORSA J. Comput. 1, 3, 181--189.

[35]

Edmonds, J. 1971. Matroids and the greedy algorithm. Math. Program. 1, 127--136.

Digital Library

[36]

Edmonds, J. and Kwon, J. 2009. A faster approximate minimum steiner tree algorithm. Based on J. Kwon's MCS thesis “Improved results on models of greedy and primal-dual algorithms.” http://www.cse.yorku.ca/~jeff/research/students/James/thesis.pdf.

[37]

Erlebach, T. and Spieksma, F. C. R. 2000. Simple algorithms for a weighted interval selection problem. In Proceedings of the International Symposium on Algorithms and Computation (ISAAC). 228--240.

Digital Library

[38]

Erlebach, T. and Spieksma, F. C. R. 2003. Interval selection: Applications, algorithms, and lower bounds. J. Algor. 46, 1, 27--53.

Digital Library

[39]

Feige, U. 1998. A threshold of ln n for approximating set cover. J. ACM 45, 4, 634--652.

Digital Library

[40]

Feige, U. and Krauthgamer, R. 2003. The probable value of the Lovasz-Schrijver relaxations for maximum independent set. SIAM J. Comput. 32, 2, 345--370.

Digital Library

[41]

Fernandez de la Vega, W. and Kenyon-Mathieu, C. 2007. Linear programming relaxations of maxcut. In Proceedings of the 18^th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'07). Society for Industrial and Applied Mathematics, Philadelphia, PA, 53--61.

Digital Library

[42]

Georgiou, K., Magen, A., Pitassi, T., and Tourlakis, I. 2010. Integrality gaps of 2-o(1) for vertex cover sdps in the lovasz--schrijver hierarchy. SIAM J. Comput. 39, 8, 3553--3570.

Digital Library

[43]

Goemans, M. X. and Williamson, D. 1995. A general approximation technique for constrained forest problems. SIAM J. Comput. 24, 296--317.

Digital Library

[44]

Gropl, C., Hougardy, S., Nierhoff, T., and Promel, H. 2002. Steiner trees in uniformly quasibipartite graph. Inf. Process. Lett. 83, 4, 195--200.

Digital Library

[45]

Hochbaum, D., Ed. 1997. Approximation Algorithms for NP-Hard Problems. In SIGACT News, Vol. 28. ACM, New York.

Digital Library

[46]

Horn, S. 2004. One-Pass algorithms with revocable acceptances for job interval selection. MSc Thesis, University of Toronto.

[47]

Jain, K. and Vazirani, V. 2001. Approximation algorithms for the metric facility location problem and k-median problem using the primal-dual schema and lagrangian relaxation. J. ACM 48, 274--299.

Digital Library

[48]

Khanna, S., Motwani, R., Sudan, M., and Vazirani, U. 1998. On syntactic versus computational views of approximability. SIAM J. Comput. 28, 164--191.

Digital Library

[49]

Klein, P. and Ravi, R. 1993. When cycles collapse: A general approximation technique for constrained two-connectivity problems. In Proceedings of the 3^rd MPS Conference on Integer Programming and Combinatorial Optimization (IPCO'93). Springer, 39--55.

[50]

Konemann, J., Pritchard, D., and Tan, K. 2011. A partition-based relaxation for steiner trees. Math. Program. 127, 2, 345--370.

Digital Library

[51]

Korte, B. and Lovasz, L. 1984. Greedoids and linear objective functions. SIAM J. Algebr. Discr. Methods 5, 229--238.

[52]

Mehlhorn, K. 1988. A faster approximation algorithm for the steiner problem in graphs. Inf. Process. Lett. 27, 3, 125--128.

Digital Library

[53]

Rajagopalan, S. and Vazirani, V. 1999. On the bidirected cut relaxation for the metric steiner tree problem. In Proceedings of the Annual ACM/SIAM Symposium on Discrete Algorithms (SODA'99). 742--751.

Digital Library

[54]

Raz, R. and Safra, S. 1997. A sub-constant error-probability low-degree test, and sub-constant error probability PCP characterization of NP. In Proceedings of the 29th Annual ACM Symposium on the Theory of Computing (STOC'97). ACM, New York, 475--484.

Digital Library

[55]

Robins, G. and Zelikovsky, A. 2005. Tighter bounds for graph steiner tree approximation. SIAM J. Discr. Math. 19, 1, 122--134.

Digital Library

[56]

Saran, H., Vazirani, V., and Young, N. 1992. A primal-dual approach to approximation algorithms for network steiner problems. In Proceedings of the Indo-US Workshop on Cooperative Research in Computer Science. 166--168.

[57]

Schoenebeck, G., Trevisan, L., and Tulsiani, M. 2007. Tight integrality gaps for Lovasz-Schrijver LP relaxations of vertex cover and max cut. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing. D. S. Johnson and U. Feige. Eds., ACM, New York, 302--310.

Digital Library

[58]

Singh, M. and Talwar, K. 2010. Improving integrality gaps via chvatal-gomory rounding. In Proceedings of the International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX-RANDOM). Lecture Notes in Computer Science, vol. 6302. Springer.

Digital Library

[59]

Slavik, P. 1997. A tight analysis of the greedy algorithm for set cover. J. Algor. 25, 237--254.

Digital Library

[60]

Vazirani, V. V. 2001. Approximation Algorithms. Springer, New York.

Digital Library

[61]

Williamson, D. P. 2002. The primal-dual method for approximation algorithms. Math. Program. B 91, 3, 447--478.

Digital Library

[62]

Ye, Y. and Borodin, A. 2009. Elimination graphs. In Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP'09). ACM, New York.

Digital Library

Cited By

Borodin ALucier B(2016)On the Limitations of Greedy Mechanism Design for Truthful Combinatorial AuctionsACM Transactions on Economics and Computation10.1145/29565855:1(1-23)Online publication date: 10-Oct-2016
https://dl.acm.org/doi/10.1145/2956585
Koufogiannakis CYoung N(2012)Greedy Δ-Approximation Algorithm for Covering with Arbitrary Constraints and Submodular CostAlgorithmica10.1007/s00453-012-9629-366:1(113-152)Online publication date: 14-Mar-2012
https://doi.org/10.1007/s00453-012-9629-3

Index Terms

How well can primal-dual and local-ratio algorithms perform?
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
      1. Combinatorial algorithms
2. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

Local ratio method on partial set multi-cover

In this paper, we study the minimum partial set multi-cover problem (PSMC). Given an element set E, a collection of subsets $${\mathcal {S}}\subseteq 2^E$$S⊆2E, a cost $$c_S$$cS on each set $$S\in {\mathcal {S}}$$SźS, a covering requirement $$r_e$$re ...
Primal---Dual Algorithms for Precedence Constrained Covering Problems

A covering problem is an integer linear program of type $$\min \{c^Tx\mid Ax\ge D,\ 0\le x\le d,\ x \in \mathbb {Z}\}$$min{cTxźAxźD,0≤x≤d,xźZ} where $$A\in \mathbb {Z}^{m\times n}_+$$AźZ+m n, $$D\in \mathbb {Z}_+^m$$DźZ+m, and $$c,d\in \mathbb {Z}_+^n$$...
Approximating the Unweighted ${k}$-Set Cover Problem: Greedy Meets Local Search

In the unweighted set cover problem we are given a set of elements $E=\{e_1,e_2,\ldots,e_n\}$ and a collection ${\cal F}$ of subsets of $E$. The problem is to compute a subcollection $SOL\subseteq{\cal F}$ such that $\bigcup_{S_j\in SOL}S_j=E$ and its ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Algorithms

ACM Transactions on Algorithms Volume 7, Issue 3

July 2011

294 pages

ISSN:1549-6325

EISSN:1549-6333

DOI:10.1145/1978782

Issue’s Table of Contents

Copyright © 2011 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 15 July 2011

Accepted: 01 March 2011

Revised: 01 March 2011

Received: 01 May 2008

Published in TALG Volume 7, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
358
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Borodin ALucier B(2016)On the Limitations of Greedy Mechanism Design for Truthful Combinatorial AuctionsACM Transactions on Economics and Computation10.1145/29565855:1(1-23)Online publication date: 10-Oct-2016
https://dl.acm.org/doi/10.1145/2956585
Koufogiannakis CYoung N(2012)Greedy Δ-Approximation Algorithm for Covering with Arbitrary Constraints and Submodular CostAlgorithmica10.1007/s00453-012-9629-366:1(113-152)Online publication date: 14-Mar-2012
https://doi.org/10.1007/s00453-012-9629-3

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents