Advertisement

A Tale of Two Methods

  • Reuven Bar-Yehuda
  • Dror Rawitz
Chapter
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3895)

Abstract

We describe two widely used methods for the design and analysis of approximation algorithms, the primal-dual schema and the local ratio technique. We focus on the creation of both methods by revisiting two results by Bar-Yehuda and Even—the linear time primal-dual approximation algorithm for set cover, and its local ratio interpretation. We also follow the evolution of the two methods by discussing more recent studies.

Keywords

Approximation Algorithm Vertex Cover Minimal Solution Dual Solution Linear Programming Relaxation 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. 1.
    Agrawal, A., Klein, P., Ravi, R.: When trees collide: An approximation algorithm for the generalized Steiner problem on networks. SIAM Journal on Computing 24(3), 440–456 (1995)zbMATHCrossRefMathSciNetGoogle Scholar
  2. 2.
    Akcoglu, K., Aspnes, J., DasGupta, B., Kao, M.-Y.: Opportunity cost algorithms for combinatorial auctions. In: Kontoghiorghes, E.J., Rustem, B., Siokos, S. (eds.) Applied Optimization: Computational Methods in Decision-Making Economics and Finance, Kluwer Academic Publishers, Dordrecht (2002)Google Scholar
  3. 3.
    Bafna, V., Berman, P., Fujito, T.: A 2-approximation algorithm for the undirected feedback vertex set problem. SIAM Journal on Discrete Mathematics 12(3), 289–297 (1999)zbMATHCrossRefMathSciNetGoogle Scholar
  4. 4.
    Bar-Noy, A., Bar-Yehuda, R., Freund, A., Naor, J., Shieber, B.: A unified approach to approximating resource allocation and schedualing. Journal of the ACM 48(5), 1069–1090 (2001)CrossRefMathSciNetGoogle Scholar
  5. 5.
    Bar-Noy, A., Guha, S., Katz, Y., Naor, J., Schieber, B., Shachnai, H.: Throughput maximization of real-time scheduling with batching. In: 13th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 742–751 (2002)Google Scholar
  6. 6.
    Bar-Yehuda, R.: One for the price of two: A unified approach for approximating covering problems. Algorithmica 27(2), 131–144 (2000)zbMATHCrossRefMathSciNetGoogle Scholar
  7. 7.
    Bar-Yehuda, R., Bendel, K., Freund, A., Rawitz, D.: Local ratio: a unified framework for approximation algorithms. ACM Computing Surveys 36(4), 422–463 (2004)CrossRefGoogle Scholar
  8. 8.
    Bar-Yehuda, R., Even, S.: A linear time approximation algorithm for the weighted vertex cover problem. Journal of Algorithms 2(2), 198–203 (1981)zbMATHCrossRefMathSciNetGoogle Scholar
  9. 9.
    Bar-Yehuda, R., Even, S.: A local-ratio theorem for approximating the weighted vertex cover problem. Annals of Discrete Mathematics 25, 27–46 (1985)MathSciNetGoogle Scholar
  10. 10.
    Bar-Yehuda, R., Halldórsson, M.M., Naor, J., Shachnai, H., Shapira, I.: Scheduling split intervals. In: 13th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 732–741 (2002)Google Scholar
  11. 11.
    Bar-Yehuda, R., Rawitz, D.: Efficient algorithms for bounded integer programs with two variables per constraint. Algorithmica 29(4), 595–609 (2001)zbMATHCrossRefMathSciNetGoogle Scholar
  12. 12.
    Bar-Yehuda, R., Rawitz, D.: Local ratio with negative weights. Operations. Operations Research Letters 32(6), 540–546 (2004)zbMATHCrossRefMathSciNetGoogle Scholar
  13. 13.
    Bar-Yehuda, R., Rawitz, D.: On the equivalence between the primal-dual schema and the local ratio technique. SIAM Journal on Discrete Mathematics (2005) (to appear)Google Scholar
  14. 14.
    Bar-Yehuda, R., Rawitz, D.: Using fractional primal-dual to schedule split intervals with demands. In: 13th Annual European Symposium on Algorithms (2005) (to appear)Google Scholar
  15. 15.
    Bertsimas, D., Teo, C.: From valid inequalities to heuristics: A unified view of primal-dual approximation algorithms in covering problems. Operations Research 46(4), 503–514 (1998)zbMATHCrossRefMathSciNetGoogle Scholar
  16. 16.
    Chudak, F.A., Goemans, M.X., Hochbaum, D.S., Williamson, D.P.: A primaldual interpretation of recent 2-approximation algorithms for the feedback vertex set problem in undirected graphs. Operations Research Letters 22, 111–118 (1998)zbMATHCrossRefMathSciNetGoogle Scholar
  17. 17.
    Chvátal, V.: A greedy heuristic for the set-covering problem. Mathematics of. Mathematics of Operations Research 4(3), 233–235 (1979)zbMATHCrossRefMathSciNetGoogle Scholar
  18. 18.
    Freund, A., Rawitz, D.: Combinatorial interpretations of dual fitting and primal fitting. In: Solis-Oba, R., Jansen, K. (eds.) WAOA 2003. LNCS, vol. 2909, pp. 137–150. Springer, Heidelberg (2004)CrossRefGoogle Scholar
  19. 19.
    Fujito, T.: A unified approximation algorithm for node-deletion problems. Discrete Applied Mathematics and Combinatorial Operations Research and Computer Science 86, 213–231 (1998)zbMATHMathSciNetGoogle Scholar
  20. 20.
    Garey, M.R., Johnson, D.S.: Computers and Intractability; A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York (1979)zbMATHGoogle Scholar
  21. 21.
    Goemans, M.X., Williamson, D.P.: A general approximation technique for constrained forest problems. SIAM Journal on Computing 24(2), 296–317 (1995)zbMATHCrossRefMathSciNetGoogle Scholar
  22. 22.
    Goemans, M.X., Williamson, D.P.: The primal-dual method for approximation algorithms and its application to network design problems. In: Hochbaum [25], ch. 4, pp. 144–191Google Scholar
  23. 23.
    Guha, S., Hassin, R., Khuller, S., Or, E.: Capacitated vertex covering. Journal of Algorithms 48(1), 257–270 (2003)zbMATHCrossRefMathSciNetGoogle Scholar
  24. 24.
    Hochbaum, D.S.: Approximation algorithms for the set covering and vertex cover problems. SIAM Journal on Computing 11(3), 555–556 (1982)zbMATHCrossRefMathSciNetGoogle Scholar
  25. 25.
    Hochbaum, D.S. (ed.): Approximation Algorithms for NP-Hard Problem. PWS Publishing Company (1997)Google Scholar
  26. 26.
    Jain, K., Mahdian, M., Markakis, E., Saberi, A., Vazirani, V.: Greedy facility location algorithms analyzed using dual-fitting with factor-revealing LP. Journal of the ACM 50(6), 795–824 (2003)CrossRefMathSciNetGoogle Scholar
  27. 27.
    Jain, K., Vazirani, V.V.: Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation. Journal of the ACM 48(2), 274–296 (2001)zbMATHCrossRefMathSciNetGoogle Scholar
  28. 28.
    Karloff, H.: Linear Programming, Progress in Theoretical Computer Science. Birkhäuser Boston (1991)Google Scholar
  29. 29.
    Papadimitriou, C.H., Steiglitz, K.: Combinatorial Optimization; Algorithms and Complexity, 5th edn. Prentice-Hall, Inc., Englewood Cliffs (1982)zbMATHGoogle Scholar
  30. 30.
    Ravi, R., Klein, P.: When cycles collapse: A general approximation technique for constrained two-connectivity problems. In: 3rd Conference on Integer Programming and Combinatorial Optimization, pp. 39–56 (1993)Google Scholar
  31. 31.
    Schrijver, A.: Theory of linear and integer programming. Wiley Publishers, Chichester (1998)zbMATHGoogle Scholar
  32. 32.
    Vazirani, V.V.: Approximation algorithms, 2nd edn. Springer, Heidelberg (2001)Google Scholar
  33. 33.
    Williamson, D.P.: The primal dual method for approximation algorithms. Mathematical Programming (Series B) 91(3), 447–478 (2002)zbMATHCrossRefGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2006

Authors and Affiliations

  • Reuven Bar-Yehuda
    • 1
  • Dror Rawitz
    • 2
  1. 1.Department of Computer ScienceTechnionHaifaIsrael
  2. 2.Caesarea Rothschild InstituteUniversity of HaifaHaifaIsrael

Personalised recommendations