nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

16. Approximation Algorithms

verfasst von : Bernhard Korte, Jens Vygen

Erschienen in: Combinatorial Optimization

Verlag: Springer Berlin Heidelberg

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

In this chapter we introduce the important concept of approximation algorithms. So far we have dealt mostly with polynomially solvable problems. In the remaining chapters we shall indicate some strategies to cope with NP-hard combinatorial optimization problems. Here approximation algorithms must be mentioned in the first place.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel NP-Completeness

Nächstes Kapitel The Knapsack Problem

Asano, T., Iwama, K., Takada, H., and Yamashita, Y. [2000]: Designing high-quality approximation algorithms for combinatorial optimization problems. IEICE Transactions on Communications/Electronics/Information and Systems E83-D (2000), 462–478

Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., and Protasi, M. [1999]: Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer, Berlin 1999

Garey, M.R., and Johnson, D.S. [1979]: Computers and Intractability; A Guide to the Theory of NP-Completeness. Freeman, San Francisco 1979, Chapter 4

Hochbaum, D.S. [1996]: Approximation Algorithms for NP-Hard Problems. PWS, Boston, 1996

Horowitz, E., and Sahni, S. [1978]: Fundamentals of Computer Algorithms. Computer Science Press, Potomac 1978, Chapter 12

Shmoys, D.B. [1995]: 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 1995

Papadimitriou, C.H. [1994]: Computational Complexity, Addison-Wesley, Reading 1994, Chapter 13

Vazirani, V.V. [2001]: Approximation Algorithms. Springer, Berlin, 2001

Williamson, D.P., and Shmoys, D.B. [2011]: The Design of Approximation Algorithms. Cambridge University Press, Cambridge 2011

Ajtai, M. [1994]: Recursive construction for 3-regular expanders. Combinatorica 14 (1994), 379–416

Alizadeh, F. [1995]: Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM Journal on Optimization 5 (1995), 13–51

Appel, K., and Haken, W. [1977]: Every planar map is four colorable; Part I; Discharging. Illinois Journal of Mathematics 21 (1977), 429–490

Appel, K., Haken, W., and Koch, J. [1977]: Every planar map is four colorable; Part II; Reducibility. Illinois Journal of Mathematics 21 (1977), 491–567

Arora, S. [1994]: Probabilistic checking of proofs and the hardness of approximation problems, Ph.D. thesis, U.C. Berkeley, 1994

Arora, S., and Kale, S. [2016]: A combinatorial, primal-dual approach to semidefinite programs. Journal of the ACM 63 (2016), Article 12

Arora, S., Lund, C., Motwani, R., Sudan, M., and Szegedy, M. [1998]: Proof verification and hardness of approximation problems. Journal of the ACM 45 (1998), 501–555

Arora, S., and Safra, S. [1998]: Probabilistic checking of proofs. Journal of the ACM 45 (1998), 70–122

Asano, T. [2006]: An improved analysis of Goemans and Williamson’s LP-relaxation for MAX SAT. Theoretical Computer Science 354 (2006), 339–353

Avidor, A., Berkovitch, I., and Zwick, U. [2006]: Improved approximation algorithms for MAX NAE-SAT and MAX SAT. Approximation and Online Algorithms – Proceedings of the 3rd WAOA workshop (2005); LNCS 3879 (Erlebach, T., Persiano, G., eds.), Springer, Berlin 2006, pp. 27–40

Bar-Yehuda, R., and Even, S. [1981]: A linear-time approximation algorithm for the weighted vertex cover problem. Journal of Algorithms 2 (1981), 198–203

Becker, A., and Geiger, D. [1996]: 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

Bellare, M., and Sudan, M. [1994]: Improved non-approximability results. Proceedings of the 26th Annual ACM Symposium on the Theory of Computing (1994), 184–193

Bellare, M., Goldreich, O., and Sudan, M. [1998]: Free bits, PCPs and nonapproximability – towards tight results. SIAM Journal on Computing 27 (1998), 804–915

Berge, C. [1961]: Färbung von Graphen, deren sämtliche bzw. deren ungerade Kreise starr sind. Wissenschaftliche Zeitschrift, Martin Luther Universität Halle-Wittenberg, Mathematisch-Naturwissenschaftliche Reihe (1961), 114–115

Berge, C. [1962]: Sur une conjecture relative au problème des codes optimaux. Communication, 13ème assemblée générale de l’URSI, Tokyo 1962

Berman, P., and Fujito, T. [1999]: On approximation properties of the independent set problem for low degree graphs. Theory of Computing Systems 32 (1999), 115–132

Brooks, R.L. [1941]: On colouring the nodes of a network. Proceedings of the Cambridge Philosophical Society 37 (1941), 194–197

Chen, J., Friesen, D.K., and Zheng, H. [1999]: Tight bound on Johnson’s algorithm for maximum satisfiability. Journal of Computer and System Sciences 58 (1999), 622–640

Chlebík, M. and Chlebíková, J. [2006]: Complexity of approximating bounded variants of optimization problems. Theoretical Computer Science 354 (2006), 320–338

Chudnovsky, M., Cornuéjols, G., Liu, X., Seymour, P., and Vus̆ković, K. [2005]: Recognizing Berge graphs. Combinatorica 25 (2005), 143–186

Chudnovsky, M., Robertson, N., Seymour, P., and Thomas, R. [2006]: The strong perfect graph theorem. Annals of Mathematics 164 (2006), 51–229

Chvátal, V. [1975]: On certain polytopes associated with graphs. Journal of Combinatorial Theory B 18 (1975), 138–154

Chvátal, V. [1979]: A greedy heuristic for the set cover problem. Mathematics of Operations Research 4 (1979), 233–235

Clementi, A.E.F., and Trevisan, L. [1999]: Improved non-approximability results for minimum vertex cover with density constraints. Theoretical Computer Science 225 (1999), 113–128

Deza, M.M., and Laurent, M. [1997]: Geometry of Cuts and Metrics. Springer, Berlin 1997

Dinur, I. [2007]: The PCP theorem by gap amplification. Journal of the ACM 54 (2007), Article 12

Dinur, I., and Safra, S. [2002]: On the hardness of approximating minimum vertex cover. Annals of Mathematics 162 (2005), 439–485

Erdős, P. [1967]: On bipartite subgraphs of graphs. Mat. Lapok. 18 (1967), 283–288

Feige, U. [1998]: A threshold of lnn for approximating set cover. Journal of the ACM 45 (1998), 634–652

Feige, U. [2004]: Approximating maximum clique by removing subgraphs. SIAM Journal on Discrete Mathematics 18 (2004), 219–225

Feige, U., and Goemans, M.X. [1995]: 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

Feige, U., Goldwasser, S., Lovász, L., Safra, S., and Szegedy, M. [1996]: Interactive proofs and the hardness of approximating cliques. Journal of the ACM 43 (1996), 268–292

Fernández-Baca, D., and Lagergren, J. [1998]: On the approximability of the Steiner tree problem in phylogeny. Discrete Applied Mathematics 88 (1998), 129–145

Fulkerson, D.R. [1972]: Anti-blocking polyhedra. Journal of Combinatorial Theory B 12 (1972), 50–71

Fürer, M., and Raghavachari, B. [1994]: Approximating the minimum-degree Steiner tree to within one of optimal. Journal of Algorithms 17 (1994), 409–423

Garey, M.R., Johnson, D.S., and Stockmeyer, L. [1976]: Some simplified NP-complete graph problems. Theoretical Computer Science 1 (1976), 237–267

Goemans, M.X., and Williamson, D.P. [1994]: New 3/4-approximation algorithms for the maximum satisfiability problem. SIAM Journal on Discrete Mathematics 7 (1994), 656–666

Goemans, M.X., and Williamson, D.P. [1995]: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM 42 (1995), 1115–1145

Grötschel, M., Lovász, L., and Schrijver, A. [1988]: Geometric Algorithms and Combinatorial Optimization. Springer, Berlin 1988

Halldórsson, M.M., and Radhakrishnan, J. [1997]: Greed is good: approximating independent sets in sparse and bounded degree graphs. Algorithmica 18 (1997), 145–163

Håstad, J. [2001]: Some optimal inapproximability results. Journal of the ACM 48 (2001), 798–859

Heawood, P.J. [1890]: Map colour theorem. Quarterly Journal of Pure Mathematics 24 (1890), 332–338

Held, S., Cook, W., and Sewell, E.C. [2012]: Maximum-weight stable sets and safe lower bounds for graph coloring. Mathematical Programming Computation 4 (2012), 363–381

Hochbaum, D.S. [1982]: Approximation algorithms for the set covering and vertex cover problems. SIAM Journal on Computing 11 (1982), 555–556

Hochbaum, D.S., and Shmoys, D.B. [1985]: A best possible heuristic for the k-center problem. Mathematics of Operations Research 10 (1985), 180–184

Holyer, I. [1981]: The NP-completeness of edge-coloring. SIAM Journal on Computing 10 (1981), 718–720

Hougardy, S., Prömel, H.J., and Steger, A. [1994]: Probabilistically checkable proofs and their consequences for approximation algorithms. Discrete Mathematics 136 (1994), 175–223

Hsu, W.L., and Nemhauser, G.L. [1979]: Easy and hard bottleneck location problems. Discrete Applied Mathematics 1 (1979), 209–216

Johnson, D.S. [1974]: Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences 9 (1974), 256–278

Khanna, S., Linial, N., and Safra, S. [2000]: On the hardness of approximating the chromatic number. Combinatorica 20 (2000), 393–415

Khot, S., and Regev, O. [2008]: Vertex cover might be hard to approximate to within 2 −ε. Journal of Computer and System Sciences 74 (2008), 335–349

Knuth, D.E. [1969]: The Art of Computer Programming; Vol. 2. Seminumerical Algorithms. Addison-Wesley, Reading 1969 (third edition: 1997)

König, D. [1916]: Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre. Mathematische Annalen 77 (1916), 453–465

Lieberherr, K., and Specker, E. [1981]: Complexity of partial satisfaction. Journal of the ACM 28 (1981), 411–421

Lovász, L. [1972]: Normal hypergraphs and the perfect graph conjecture. Discrete Mathematics 2 (1972), 253–267

Lovász, L. [1975]: On the ratio of optimal integral and fractional covers. Discrete Mathematics 13 (1975), 383–390

Lovász, L. [1979a]: On the Shannon capacity of a graph. IEEE Transactions on Information Theory 25 (1979), 1–7

Lovász, L. [1979b]: 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–158

Lovász, L. [2003]: Semidefinite programs and combinatorial optimization. In: Recent Advances in Algorithms and Combinatorics (B.A. Reed, C. Linhares Sales, eds.), Springer, New York 2003, pp. 137–194

Mahajan, S., and Ramesh, H. [1999]: Derandomizing approximation algorithms based on semidefinite programming. SIAM Journal on Computing 28 (1999), 1641–1663

Papadimitriou, C.H., and Steiglitz, K. [1982]: Combinatorial Optimization; Algorithms and Complexity. Prentice-Hall, Englewood Cliffs 1982, pp. 406–408

Papadimitriou, C.H., and Yannakakis, M. [1991]: Optimization, approximation, and complexity classes. Journal of Computer and System Sciences 43 (1991), 425–440

Papadimitriou, C.H., and Yannakakis, M. [1993]: The traveling salesman problem with distances one and two. Mathematics of Operations Research 18 (1993), 1–12

Raghavan, P., and Thompson, C.D. [1987]: Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica 7 (1987), 365–374

Raz, R., and Safra, S. [1997]: 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

Robertson, N., Sanders, D.P., Seymour, P., and Thomas, R. [1997]: The four colour theorem. Journal of Combinatorial Theory B 70 (1997), 2–44

Sanders, P., and Steurer, D. [2008]: An asymptotic approximation scheme for multigraph edge coloring. ACM Transactions on Algorithms 4 (2008), Article 21

Singh, M. and Lau, L.C. [2015]: Approximating minimum bounded degree spanning trees to within one of optimal. Journal of the ACM 62 (2015), Article 1

Slavík, P. [1997]: A tight analysis of the greedy algorithm for set cover. Journal of Algorithms 25 (1997), 237–254

Stockmeyer, L.J. [1973]: Planar 3-colorability is polynomial complete. ACM SIGACT News 5 (1973), 19–25

Trevisan, L. [2004]: On local versus global satisfiability. SIAM Journal on Discrete Mathematics 17 (2004), 541–547

Vizing, V.G. [1964]: On an estimate of the chromatic class of a p-graph. Diskret. Analiz 3 (1964), 23–30 [in Russian]

Wigderson, A. [1983]: Improving the performance guarantee for approximate graph coloring. Journal of the ACM 30 (1983), 729–735

Yannakakis, M. [1994]: On the approximation of maximum satisfiability. Journal of Algorithms 17 (1994), 475–502

Zuckerman, D. [2007]: Linear degree extractors and the inapproximability of Max Clique and Chromatic Number. Theory of Computing 3 (2007), 103–128

Titel: Approximation Algorithms
verfasst von: Bernhard Korte
Jens Vygen
Verlag: Springer Berlin Heidelberg
Buch: Combinatorial Optimization
Print ISBN: 978-3-662-56038-9

Electronic ISBN: 978-3-662-56039-6

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-662-56039-6_16

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"