Approximation Algorithms for NP-problems
Abstract
Algorithms are at the heart of problem solving in scientific computing and computer science. Unfortunately many of the combinatorial problems that arise in a computational context are NP-hard, so that optimal solutions are unlikely to be found in polynomial time. How can we cope with this intractability? One approach is to design algorithms that find approximate solutions guaranteed to be within some factor of the quality of the optimal solution. More recently, in large-scale scientific computing, even polynomial time algorithms that find exact solutions are deemed too expensive to be practical, and one needs faster (nearly linear time)approximation algorithms. We will consider the design of
approximation algorithms for various graph-theoretical and
combinatorial problems that commonly arise in scientific computing and computational biology. These include set covers (vertex covers in hypergraphs), matching, coloring, and multiple sequence alignments in computational biology.
Keywords
Full Text:
PDFReferences
G. Ausiello, C. Bazgan, M. Demange, and V. Th. Paschos.Completeness in differential approximation classes. Cahier du LAMSADE 204, LAMSADE, Université Paris-Dauphine, 2003. Available on http://www.lamsade.dauphine.fr/cahiers.html.
G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi, “Complexity and approximation.Combinatorial optimization problems and their approximability properties”, Springer, Berlin, 1999.
G. Ausiello, P. Crescenzi, and M. Protasi, Approximate solutions of NP optimization problems, Theoret. Comput. Sci., 150:1-55, 1995.
S. A. Cook, The complexity of theorem-proving procedures. In Proc.STOC'71, 151-158, 1971.
P. Crescenzi and A. Panconesi, Completeness in approximation classes,Inform. and Comput, 93(2):241262,1991.
M. Demange and V. Th. Paschos, On an approximation measure founded on the links between optimization and polynomial approximation theory, Theoret. Comput. Sci.,158:117-141, 1996.
M. R. Garey and D. S. Johnson, “Computers and intractability. A guide to the theory of NP-completeness”, H. Freeman, San Francisco, 1979.
S. Hochbaum, editor. “Approximation algorithms for NPhard problems”,PWS, Boston, 1997.
Monnot, V. Th. Paschos, and S. Toulouse, Differential approximation results for the traveling salesman problem with distances 1 and 2,European J. Oper. Res., 145(3):557--568, 2002
J. Monnot, V. Th. Paschos, and S. Toulouse, “Approximation polynomiale des problèmes NP-difficiles: optima locaux et rapport différentiel”, Informatique et Systèmes d'Information, Hermès, Paris,2003
C. H. Papadimitriou and K. Steiglitz, “Combinatorial optimization:algorithms and complexity”, Prentice Hall, New Jersey, 1981.
W.R. Gilks, S. Richardson, and D. J. Spiegelhalter, editors. Markov Chain Monte Carlo in Practice.Chapman and Hall, Suffolk, 1996.
W. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller, and E. Teller. Equations of state calculations by fast computing machines.Journal of Chemical Physics, 21:1087 1092, 1953.
W. K. Hastings. Monte Carlo sampling methods using Markov chains and their applications. Biometrika, 57:97–109, 1970.
Barker. Monte Carlo calculations of the radial distribution functions for a proton-electron plasma. Australian Journal of Physics, 18:119–133,1965.
DOI: http://dx.doi.org/10.36039/AA052009001
Refbacks
- There are currently no refbacks.
This work is licensed under a Creative Commons Attribution 3.0 License.