Top

Published in:

2014 | OriginalPaper | Chapter

21. Approximations and Randomization

Authors : Carla P. Gomes, Ryan Williams

Published in: Search Methodologies

Publisher: Springer US

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In response to the apparent intractability of NP-hard problems, approximation algorithms were introduced as a way to provide strong guarantees about the quality of solutions, without requiring exponential time to obtain them. The study of randomized algorithms, procedures that “flip coins” and are allowed to err with some probability, arose alongside approximation algorithms as a possible resource for circumventing intractability. We outline some of the various types of approximation algorithms that have been proposed, with a special focus on ones using randomization, and suggest further research directions in this area.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

previous chapter Hyper-heuristics

next chapter Fitness Landscapes

Agrawal M, Kayal N, Saxena N (2004) PRIMES is in P. Ann Math 160:781–793CrossRef

Aho AV, Hopcroft JE, Ullman JD (1979) Computers and intractability: a guide to NP-completeness. Freeman, San Francisco

Aho AV, Hopcroft JE, Ullman JD (1983) Data structures and algorithms. Computer science and information processing series. Addison-Wesley, Reading

Alon N, Spencer J (2000) The probabilistic method. Wiley, New YorkCrossRef

Arora S (1998) Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J ACM 45:753–782CrossRef

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

Arora S, Barak B, Steurer D (2010) Subexponential algorithms for unique games and related problems. In: Proceedings of the IEEE symposium on foundations of computer science, Las Vegas, pp 563–572

Ausiello G, Crescenzi P, Gambosi G, Kann V, Marchetti-Spaccamela A, Protasi M (1999) Complexity and approximation. Springer, BerlinCrossRef

Beier R, Vocking B (2003) Random knapsack in expected polynomial time. J Comput Syst Sci 69:306–329CrossRef

Chazelle B (2001) The discrepancy method. Cambridge University Press, Cambridge/New York

Chvatal V (1979) A greedy heuristic for the set-covering. Math Oper Res 4:233–235CrossRef

Chvatal V (1983) Linear programming. Freeman, San Francisco

Clay Mathematics Institute (2003) The millenium prize problems: P vs NP. http://www.claymath.org/

Colbourn C (1984) The complexity of completing partial latin squares. Discret Appl Math 8:25–30CrossRef

Cook W, Cunningham W, Pulleyblank W, Schrijver A (1988) Combinatorial optimization. Wiley, New York

Cormen TH, Leiserson CE, Rivest RL, Stein C (2001) Introduction to algorithms. MIT, Cambridge

Dantzig G (1998) Linear programming and extensions. Princeton University Press, Princeton

Dantzig GB, Ford LR, Fulkerson DR (1956) A primal-dual algorithm for linear programs. In: Kuhn HW, Tucker AW (eds) Linear inequalities and related systems, Annals ofMathematics Study No. 38, Princeton University Press, Princeton, New Jersey, pp 171–181

Egerváry E (1931) Matrixok kombinatorius tujajdonsagairol. Matematikai es Fizikai Lapok 38:16–28

Feige U (2002) Relations between average case complexity and approximation complexity. In: Proceedings of the ACM symposium on theory of computing, Montreal

Feller W (1971) An introduction to probability theory and its applications. Wiley, New York

Garey MR, Graham RL, Ulman JD (1972) Worst case analysis of memory allocation algorithms. In: Proceedings of the 4th ACM symposium on theory of computing, Denver, pp 143–150

Goemans MX, Williamson DP (1995) Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J ACM 42:1115–1145CrossRef

Goemans M, Williamson DP (1997) The primal-dual method for approximation algorithms and its application to network design problems. In: Hochbaum DS (ed) Approximation algorithms for NP-hard problems. PWS, Boston

Goldwasser S, Kilian J (1986) Almost all primes can be quickly certified. In: Proceedings of the annual IEEE symposium on foundations of computer science, Toronto, pp 316–329

Gomes CP, Shmoys D (2002) The promise of LP to boost CSP techniques for combinatorial problems. In: Jussien N, Laburthe F (eds) Proceedings of the CP-AI-OR 2002, Le Croisic, France, pp 291–305. http://www.emn.fr/z-info/cpaior/

Gomes CP, Selman B, Kautz H (1998) Boosting combinatorial search through randomization. In: Proceedings of the AAAI 1998, Madison, Wisconsin, pp 431–437. http://www.aaai.org/Conferences/AAAI/aaai98.php

Gomes C, Selman B, Crato N, Kautz H (2000) Heavy-tailed phenomena in satisfiability and constraint satisfaction problems. J Autom Reason 24:67–100CrossRef

Graham RL (1966) Bounds for certain multiprocessing anomalies. Bell Syst Tech J 45:1563–1581CrossRef

Hochbaum DS (1982) Approximation algorithms for the set covering and vertex cover problem. SIAM J Comput 11:555–556CrossRef

Hochbaum DS (1983) Efficient bounds for the stable set, vertex cover and the set packing problems. Discret Appl Math 6:243–254CrossRef

Hochbaum DS (ed) (1997) Approximation algorithms for NP-hard problems. PWS, Boston

Johnson DS (1974) Approximation algorithms for combinatorial problems. J Comput Syst Sci 9:256–278CrossRef

Khot S (2002) On the power of unique 2-prover 1-round games. In: Proceedings of the 34th annual ACM symposium on theory of computing, Montreal, pp 767–775

Khot S, Regev O (2003) Vertex cover might be hard to approximate within 2 −ε. In: Proceedings of the IEEE conference on computational complexity, Aarhus. J Comput Syst Sci 74:335–349CrossRef

Kirkpatrick S, Gelatt C, Vecchi M (1983) Optimization by simulated annealing. Science 220:671–680CrossRef

Kozen D (1992) The design and analysis of algorithms. Springer, New YorkCrossRef

Kuhn HW (1955) The Hungarian method for the assignment problem. Nav Res Q 2:83–97CrossRef

Kumar SR, Russell A, Sundaram R (1999) Approximating latin square extensions. Algorithmica 24:128–138CrossRef

Laywine C, Mullen G (1998) Discrete mathematics using latin squares. Discrete mathematics and optimization series. Wiley-Interscience, New York

Lovasz L (1975) On the ratio of optimal integral and fractional covers. Discret Math 13:383–390CrossRef

Motwani R, Raghavan P (1995) Randomized algorithms. Cambridge University Press, Cambridge/New YorkCrossRef

Nemhauser G, Wolsey L (1988) Integer and combinatorial optimization. Wiley, New York

Papadimitriou C, Steiglitz K (1982) Combinatorial optimization: algorithms and complexity. Prentice-Hall, Englewood Cliffs

Rabin M (1980) Probabilistic algorithm for testing primality. J Number Theor 12:128–138CrossRef

Schrijver A (2003) Combinatorial optimization polyhedra and efficiency. Springer, Berlin

Shmoys D (1995) Computing near-optimal solutions to combinatorial optimization problems. In: Cook W, Lovasz L, Seymour P (eds) Combinatorial optimization. DIMACS series. AMS, Providence, pp 355–396

Solovay R, Strassen V (1977) A fast Monte Carlo test for primality. SIAM J Comput 6:84–86CrossRef

Srinivasan A (1999) Approximation algorithms via randomized rounding: a survey. In: Karonskin M, Promel HJ (eds) Lectures on approximation and randomized algorithms. Series in advanced topics in mathematics. Polish Scientific Publishers PWN, Warsaw, pp 9–71

Vazirani V (2004) Approximation algorithms. Springer, Berlin

Williams R, Gomes CP, Selman B (2003) Backdoors to typical case complexity. In: Proceedings of the IJCAI, Acapulco, pp 173–1178

Williamson DP, Shmoys DB (2011) The design of approximation algorithms. Cambridge University Press, New YorkCrossRef

Wolsey LA (1980) Heuristic analysis, linear programming and branch and bound. Math Programm 28:271–287

Title: Approximations and Randomization
Authors: Carla P. Gomes
Ryan Williams
Publisher: Springer US
Book: Search Methodologies
Print ISBN: 978-1-4614-6939-1

Electronic ISBN: 978-1-4614-6940-7

Copyright Year: 2014
DOI: https://doi.org/10.1007/978-1-4614-6940-7_21

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"