Why do we need an approximation algorithm

Approximation algorithms

Combinatorial Optimization pp 423-471 | Cite as

Summary

In this chapter we introduce the very important concept of the approximation algorithm. So far we have mainly considered polynomial solvable problems. In the remaining chapters, we'll cover some strategies for handling NP-Discuss difficult combinatorial optimization problems. In the first place are the approximation algorithms.

This is a preview of subscription content, log in to check access.

Preview

Unable to display preview. Download preview PDF.

literature

General literature

  1. Asano, T., Iwama, K., Takada, H., and Yamashita, Y .: Designing high-quality approximation algorithms for combinatorial optimization problems. IEICE Transactions on Communications / Electronics / Information and Systems E83-D (2000), 462-478 Google Scholar
  2. Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., and Protasi, M .: Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer, Berlin 1999zbMATHGoogle Scholar
  3. Garey, M.R., and Johnson, D.S .: Computers and Intractability; A Guide to the Theory of NP Completeness. Freeman, San Francisco 1979, Chapter 4zbMATHGoogle Scholar
  4. Hochbaum, D.S .: Approximation Algorithms for NP-Hard Problem. PWS, Boston, 1996Google Scholar
  5. Horowitz, E., and Sahni, S .: Fundamentals of Computer Algorithms. Computer Science Press, Potomac 1978, Chapter 12zbMATHGoogle Scholar
  6. Shmoys, D.B .: Computing near-optimal solutions to combinatorial optimization problems. In: Combinatorial Optimization; DIMACS Series in Discrete Mathematics and Theoretical Computer Science 20 (W. Cook, L. Lovász, P. Seymour, eds.), AMS, Providence 1995Google Scholar
  7. Papadimitriou, C.H .: Computational Complexity, Addison-Wesley, Reading 1994, Chapter 13zbMATHGoogle Scholar
  8. Vazirani, V.V .: Approximation Algorithms. Springer, Berlin, 2001Google Scholar

Literature cited

  1. Ajtai, M .: Recursive construction for 3-regular expanders. Combinatorica 14 (1994), 379-416zbMATHCrossRefMathSciNetGoogle Scholar
  2. Alizadeh, F .: Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM Journal on Optimization 5 (1995), 13-51zbMATHCrossRefMathSciNetGoogle Scholar
  3. Appel, K., and Haken, W .: Every planar map is four colorable; Part I; Discharging. Illinois Journal of Mathematics 21 (1977), 429-490zbMATHMathSciNetGoogle Scholar
  4. Appel, K., Haken, W., and Koch, J .: Every planar map is four colorable; Part II; Reducibility. Illinois Journal of Mathematics 21 (1977), 491-567zbMATHMathSciNetGoogle Scholar
  5. Arora, S .: Probabilistic checking of proofs and the hardness of approximation problems, Ph.D. thesis, U.C. Berkeley, 1994Google Scholar
  6. Arora, S., Lund, C., Motwani, R., Sudan, M., and Szegedy, M .: Proof verification and hardness of approximation problems. Journal of the ACM 45 (1998), 501-555zbMATHCrossRefMathSciNetGoogle Scholar
  7. Arora, S., and Safra, S .: Probabilistic checking of proofs. Journal of the ACM 45 (1998), 70-122zbMATHCrossRefMathSciNetGoogle Scholar
  8. Asano, T .: An improved analysis of Goemans and Williamson’s LP-relaxation for MAX SAT. Theoretical Computer Science 354 (2006), 339–353zbMATHCrossRefMathSciNetGoogle Scholar
  9. Bar-Yehuda, R., and Even, S .: A linear-time approximation algorithm for the weighted vertex cover problem. Journal of Algorithms 2 (1981), 198-203zbMATHCrossRefMathSciNetGoogle Scholar
  10. Becker, A., and Geiger, D .: Optimization of Pearl’s method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem. Artificial Intelligence Journal 83 (1996), 1-22 CrossRefMathSciNetGoogle Scholar
  11. Bellare, M., and Sudan, M .: Improved non-approximability results. Proceedings of the 26th Annual ACM Symposium on the Theory of Computing (1994), 184-193 Google Scholar
  12. Bellare, M., Goldreich, O., and Sudan, M .: Free bits, PCPs and nonapproximability - towards tight results. SIAM Journal on Computing 27 (1998), 804–915zbMATHCrossRefMathSciNetGoogle Scholar
  13. Berge, C .: Coloring of graphs whose all or their odd circles are rigid. Scientific journal, Martin Luther University Halle-Wittenberg, Mathematical-Natural Science Series (1961), 114–115Google Scholar
  14. Berge, C .: Sur une conjecture relative au probème des codes optimaux. Communication, 13ème assemblée générale de l’URSI, Tokyo 1962Google Scholar
  15. Berman, P., and Fujito, T .: On approximation properties of the independent set problem for low degree graphs. Theory of Computing Systems 32 (1999), 115-132zbMATHCrossRefMathSciNetGoogle Scholar
  16. Brooks, R.L .: On coloring the nodes of a network. Proceedings of the Cambridge Philosophical Society 37 (1941), 194-197MathSciNetGoogle Scholar
  17. Chen, J., Friesen, D.K., and Zheng, H .: Tight bound on Johnson’s algorithm for maximum satisfiability. Journal of Computer and System Sciences 58 (1999), 622-640zbMATHCrossRefMathSciNetGoogle Scholar
  18. Chlebík, M. and Chlebíková, J .: Complexity of approximating bounded variants of optimization problems. Theoretical Computer Science 354 (2006), 320-338zbMATHCrossRefMathSciNetGoogle Scholar
  19. Chudnovsky, M., Cornuéjols, G., Liu, X., Seymour, P., and Vuškovi´c, K .: Recognizing Berge graphs. Combinatorica 25 (2005), 143-186zbMATHCrossRefMathSciNetGoogle Scholar
  20. Chudnovsky, M., Robertson, N., Seymour, P., and Thomas, R .: The strong perfect graph theorem. Annals of Mathematics 164 (2006), 51-229zbMATHMathSciNetGoogle Scholar
  21. Chvátal, V .: On certain polytopes associated with graphs. Journal of Combinatorial Theory B 18 (1975), 138-154zbMATHCrossRefGoogle Scholar
  22. Chvátal, V .: A greedy heuristic for the set cover problem. Mathematics of Operations Research 4 (1979), 233-235zbMATHMathSciNetGoogle Scholar
  23. Clementi, A.E.F., and Trevisan, L .: Improved non-approximability results for minimum vertex cover with density constraints. Theoretical Computer Science 225 (1999), 113-128zbMATHCrossRefMathSciNetGoogle Scholar
  24. Deza, M.M., and Laurent, M .: Geometry of Cuts and Metrics. Springer, Berlin 1997zbMATHGoogle Scholar
  25. Dinur, I .: The PCP theorem by gap amplification. Journal of the ACM 54 (2007), Article 12 Google Scholar
  26. Dinur, I., and Safra, S .: On the hardness of approximating minimum vertex cover. Annals of Mathematics 162 (2005), 439–485zbMATHMathSciNetGoogle Scholar
  27. Erdős, P .: On bipartite subgraphs of graphs. Mat. Lapok. 18 (1967): 283-288 MathSciNetGoogle Scholar
  28. Feige, U .: A threshold of ln n for the approximating set cover. Journal of the ACM 45 (1998), 634-652zbMATHCrossRefMathSciNetGoogle Scholar
  29. Feige, U .: Approximating maximum clique by removing subgraphs. SIAM Journal on Discrete Mathematics 18 (2004), 219–225zbMATHCrossRefMathSciNetGoogle Scholar
  30. Feige, U., and Goemans, M.X .: Approximating the value of two prover proof systems, with applications to MAX 2SAT and MAX DICUT. Proceedings of the 3rd Israel Symposium on Theory of Computing and Systems (1995), 182-189 Google Scholar
  31. Feige, U., Goldwasser, S., Lovász, L., Safra, S., and Szegedy, M .: Interactive proofs and the hardness of approximating cliques. Journal of the ACM 43 (1996), 268-292zbMATHCrossRefMathSciNetGoogle Scholar
  32. Fernández-Baca, D., and Lagergren, J .: On the approximability of the Steiner tree problem in phylogeny. Discrete Applied Mathematics 88 (1998), 129-145zbMATHCrossRefMathSciNetGoogle Scholar
  33. Fulkerson, D.R .: Anti-blocking polyhedra. Journal of Combinatorial Theory B 12 (1972), 50-71zbMATHCrossRefMathSciNetGoogle Scholar
  34. Fürer, M., and Raghavachari, B .: Approximating the minimum-degree Steiner tree to within one of optimal. Journal of Algorithms 17 (1994), 409-423 CrossRefMathSciNetGoogle Scholar
  35. Garey, M.R., and Johnson, D.S .: The complexity of near-optimal graph coloring. Journal of the ACM 23 (1976), 43-49zbMATHCrossRefMathSciNetGoogle Scholar
  36. Garey, M.R., Johnson, D.S., and Stockmeyer, L .: Some simplified NP-complete graph problems. Theoretical Computer Science 1 (1976), 237-267zbMATHCrossRefMathSciNetGoogle Scholar
  37. Goemans, M.X., and Williamson, D.P .: New 3/4 approximation algorithms for the maximum satisfiability problem. SIAM Journal on Discrete Mathematics 7 (1994), 656-666zbMATHCrossRefMathSciNetGoogle Scholar
  38. Goemans, M.X., and Williamson, D.P .: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM 42 (1995), 1115-1145zbMATHCrossRefMathSciNetGoogle Scholar
  39. Grötschel, M., Lovász, L., and Schrijver, A .: Geometric Algorithms and Combinatorial Optimization. Springer, Berlin 1988zbMATHGoogle Scholar
  40. Halldórsson, M.M., and Radhakrishnan, J .: Greed is good: approximating independent sets in sparse and bounded degree graphs. Algorithmica 18 (1997), 145-163zbMATHCrossRefMathSciNetGoogle Scholar
  41. Håstad, J .: Some optimal inapproximability results. Journal of the ACM 48 (2001), 798-859zbMATHCrossRefMathSciNetGoogle Scholar
  42. Heawood, P.J .: Map color theorem. Quarterly Journal of Pure Mathematics 24 (1890), 332–338Google Scholar
  43. Hochbaum, D.S .: Approximation algorithms for the set covering and vertex cover problems. SIAM Journal on Computing 11 (1982), 555-556zbMATHCrossRefMathSciNetGoogle Scholar
  44. Hochbaum, D.S., and Shmoys, D.B .: A best possible heuristic for the k-center problem. Mathematics of Operations Research 10 (1985), 180-184zbMATHMathSciNetCrossRefGoogle Scholar
  45. Holyer, I .: The NP-completeness of edge coloring. SIAM Journal on Computing 10 (1981), 718-720zbMATHCrossRefMathSciNetGoogle Scholar
  46. Hougardy, S., Prömel, H.J., and Steger, A .: Probabilistically checkable proofs and their consequences for approximation algorithms. Discrete Mathematics 136 (1994), 175-223zbMATHCrossRefMathSciNetGoogle Scholar
  47. Hsu, W.L., and Nemhauser, G.L .: Easy and hard bottleneck location problems. Discrete Applied Mathematics 1 (1979), 209-216zbMATHCrossRefMathSciNetGoogle Scholar
  48. Johnson, D.S .: Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences 9 (1974), 256-278zbMATHMathSciNetCrossRefGoogle Scholar
  49. Khanna, S., Linial, N., and Safra, S .: On the hardness of approximating the chromatic number. Combinatorica 20 (2000), 393-415zbMATHCrossRefMathSciNetGoogle Scholar
  50. Knuth, D.E .: The Art of Computer Programming; Vol. 2. Seminumerical Algorithms. Addison-Wesley, Reading 1969 (third edition: 1997) König, D .: About graphs and their application to determinant theory and set theory. Mathematische Annalen 77 (1916), 453-465Google Scholar
  51. Lieberherr, K., and Specker, E .: Complexity of partial satisfaction. Journal of the ACM 28 (1981), 411-421zbMATHCrossRefMathSciNetGoogle Scholar
  52. Lovász, L .: Normal hypergraphs and the perfect graph conjecture. Discrete Mathematics 2 (1972), 253-267zbMATHCrossRefMathSciNetGoogle Scholar
  53. Lovász, L .: On the ratio of optimal integral and fractional covers. Discrete Mathematics 13 (1975), 383-390zbMATHCrossRefMathSciNetGoogle Scholar
  54. Lovász, L .: On the Shannon capacity of a graph. IEEE Transactions on Information Theory 25 (1979), 1-7zbMATHCrossRefGoogle Scholar
  55. Lovász, L .: Graph theory and integer programming. In: Discrete Optimization I; Annals of Discrete Mathematics 4 (P.L. Hammer, E.L. Johnson, B.H. Korte, eds.), North-Holland, Amsterdam 1979, pp. 141-158Google Scholar
  56. Lovász, L .: Semidefinite programs and combinatorial optimization. In: Recent Advances in Algorithms and Combinatorics (B.A. Reed, C.L. Sales, eds.), Springer, New York (2003), pp. 137-194 CrossRefGoogle Scholar
  57. Mahajan, S., and Ramesh, H .: Derandomizing approximation algorithms based on semidefinite programming. SIAM Journal on Computing 28 (1999), 1641–1663zbMATHCrossRefMathSciNetGoogle Scholar
  58. Papadimitriou, C.H., and Steiglitz, K .: Combinatorial Optimization; Algorithms and Complexity. Prentice-Hall, Englewood Cliffs 1982, pp. 406-408zbMATHGoogle Scholar
  59. Papadimitriou, C.H., and Yannakakis, M .: Optimization, approximation, and complexity classes. Journal of Computer and System Sciences 43 (1991), 425-440zbMATHCrossRefMathSciNetGoogle Scholar
  60. Papadimitriou, C.H., and Yannakakis, M .: The traveling salesman problem with distances one and two. Mathematics of Operations Research 18 (1993), 1-12zbMATHMathSciNetGoogle Scholar
  61. Raghavan, P., and Thompson, C.D .: Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica 7 (1987), 365-374zbMATHCrossRefMathSciNetGoogle Scholar
  62. Raz, R., and Safra, S .: A sub constant error probability low degree test, and a sub constant error probability PCP characterization of NP. Proceedings of the 29th Annual ACM Symposium on Theory of Computing (1997), 475-484 Google Scholar
  63. Robertson, N., Sanders, D.P., Seymour, P., and Thomas, R .: Efficiently four-coloring planar graphs. Proceedings of the 28th Annual ACM Symposium on the Theory of Computing (1996), 571-575 Google Scholar
  64. Robertson, N., Sanders, D.P., Seymour, P., and Thomas, R .: The four color theorem. Journal of Combinatorial Theory B 70 (1997), 2-44zbMATHCrossRefMathSciNetGoogle Scholar
  65. Sanders, P., and Steurer, D .: An asymptotic approximation scheme for multigraph edge coloring. Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (2005), 897-906 Google Scholar
  66. Singh, M. and Lau, L.C .: Approximating minimum bounded degree spanning trees to within one of optimal. Proceedings of the 39th Annual ACM Symposium on Theory of Computing (2007), 661-670 Google Scholar
  67. Slavík, P .: A tight analysis of the greedy algorithm for set cover. Journal of Algorithms 25 (1997), 237-254zbMATHCrossRefMathSciNetGoogle Scholar
  68. Stockmeyer, L.J .: Planar 3-colorability is polynomial complete. ACM SIGACT News 5 (1973), 19-25 CrossRefGoogle Scholar
  69. Trevisan, L .: On local versus global satisfiability. SIAM Journal on Discrete Mathematics 17 (2004), 541-547zbMATHCrossRefMathSciNetGoogle Scholar
  70. Vizing, V.G .: On an estimate of the chromatic class of a p-graph. Discreet. Analiz 3 (1964), 23-30 [in Russian] MathSciNetGoogle Scholar
  71. Wigderson, A .: Improving the performance guarantee for approximate graph coloring. Journal of the ACM 30 (1983), 729-735zbMATHCrossRefMathSciNetGoogle Scholar
  72. Yannakakis, M .: On the approximation of maximum satisfiability. Journal of Algorithms 17 (1994), 475-502zbMATHCrossRefMathSciNetGoogle Scholar
  73. Zuckerman, D .: Linear degree extractors and the inapproximability of Max Clique and Chromatic Number. Proceedings of the 38th Annual ACM Symposium on Theory of Computing (2006), 681-690 Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2008