An overview on polynomial approximation of NP-hard problems
DOI:
https://doi.org/10.2298/YJOR0901003PKeywords:
computational complexity, approximation algorithmsAbstract
The fact that polynomial time algorithm is very unlikely to be devised for an optimal solving of the NP-hard problems strongly motivates both the researchers and the practitioners to try to solve such problems heuristically, by making a trade-off between computational time and solution's quality. In other words, heuristic computation consists of trying to find not the best solution but one solution which is 'close to' the optimal one in reasonable time. Among the classes of heuristic methods for NP-hard problems, the polynomial approximation algorithms aim at solving a given NP-hard problem in poly-nomial time by computing feasible solutions that are, under some predefined criterion, as near to the optimal ones as possible. The polynomial approximation theory deals with the study of such algorithms. This survey first presents and analyzes time approximation algorithms for some classical examples of NP-hard problems. Secondly, it shows how classical notions and tools of complexity theory, such as polynomial reductions, can be matched with polynomial approximation in order to devise structural results for NP-hard optimization problems. Finally, it presents a quick description of what is commonly called inapproximability results. Such results provide limits on the approximability of the problems tackled.References
Arora, S., “Polynomial time approximation schemes for Euclidean TSP and other geometric problems”, in: Proc. FOCS'96, 1996, 2-11.
Arora, S., Lund, C., Motwani, R., Sudan, M., and Szegedy, M., “Proof verification and intractability of approximation problems”, J. Assoc. Comput. Mach., 45 (3) 1998, 501-555.
Aspvall, B., and Stone, R.E., “K hachiyan's linear programming algorithm”, J. Algorithms, 1 (1980), 1980, 1-13.
Ausiello, G., Bazgan, C., Demange, M., and Paschos, Th.V., “Completeness in differential approximation classes”, International Journal of Foundations of Computer Science, 16 (6) 2005, 1267-1295.
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-Verlag, Berlin, 1999.
Ausiello, G., D'Atri, A., and Protasi, M., “Structure preserving reductions among convex optimization problems”, J. Comput. System Sci., 21 (1980) 136-153.
Ausiello, G., D'Atri, A., and Protasi, M., “Lattice-theoretical ordering properties for NP complete optimization problems”, Fundamenta Informaticæ, 4 (1981) 83-94.
Ausiello, G., and Paschos, Th.V., “Reductions, completeness and the hardness of approximability”, European J. Oper. Res., 172 (2006) 719-739, Invited review.
Ausiello, G., and Paschos, Th.V., “Reductions that preserve approximability”, in: T.F. Gonzalez, (ed), Handbook of approximation algorithms and metaheuristics, chapter 15, Chapman & Hall, Boca Raton, (2007) 15-16.
Bar-Yehuda, R., and Even, S., “A local-ratio theorem for the weighted vertex cover problem”, Ann. Discrete Appl. Math., 25 (1985) 27-46.
Bazgan, C., Escoffier, B., and Paschos, Th.V., “Completeness in standard approximation classes: Poly-(D)APX- and (D)PTAS-completeness”, Theoret. Comput. Sci., 339 (2005) 272-292.
Bazgan, C., Monnot, J., Paschos, Th.V., and Serriθre, F., “On the differential approximation of min set cover”, Theoret. Comput. Sci., 332 (2005) 497-513.
Bazgan, C., and Paschos, Th.V., “Differential approximation for optimal satisfiability and related problems”, European J. Oper. Res., 147 (2) (2003) 397-404.
Bell, E.T., The Development of Mathematics, Dover, 1992.
Bellare, M., Goldreich, O., and Sudan, M., “Free bits and non-approximability - towards tight results”, SIAM J. Comput., 27 (3) (1998) 804-915.
Berge, C., Graphs and Hypergraphs, North Holland, Amsterdam, 1973.
Berman, P., and Karpinski, M., “8/7-approximation algorithm for (1,2)-TSP”, in: Proc. Symposium on Discrete Algorithms, SODA'06, 2006, 641-648.
Brooks, R.L., “On coloring the nodes of a network”, Math. Proc. Cambridge Philos. Soc., 37 (1941) 194-197.
Christofides, N., “Worst-case analysis of a new heuristic for the traveling salesman problem”, Technical Report 388, Grad. School of Industrial Administration, CMU, 1976.
Chvátal, V., “A greedy heuristic for the set covering problem”, Math. Oper. Res., 4 (1979) 233-235.
Cook, S.A., “The complexity of theorem-proving procedures”, in: Proc. STOC'71, 1971, 151-158.
Crescenzi, P., “A short guide to approximation preserving reductions”, in: Proc. Conference on Computational Complexity, 1997, 262-273.
Crescenzi, P., Kann, V., Silvestri, R., and Trevisan, L., “Structure in approximation classes”, SIAM J. Comput., 28 (5) (1999) 1759-1782.
Crescenzi, P., and Panconesi, A., “Completeness in approximation classes”, Information and Computation, 93 (2) (1991) 241-262.
Croes, A., “A method for solving traveling-salesman problems”, Oper. Res., 5 (1958) 791-812.
Demange, M., De Werra, D., Monnot, J., and Paschos, V.Th., “Time slot scheduling of compatible jobs”, J. Scheduling, 10 (2007) 111-127.
Demange, M., and Paschos, V.Th., “On an approximation measure founded on the links between optimization and polynomial approximation theory”, Theoret. Comput. Sci., 158 (1996) 117-141.
Demange, M., and Paschos, V.Th., “Improved approximations for maximum independent set via approximation chains”, Appl. Math. Lett., 10 (3) (1997) 105-110.
Demange, M., and Paschos, V.Th., “Improved approximations for weighted and unweighted graph problems”, Theory of Computing Systems, 38 (2005) 763-787.
Escoffier, B., and Monnot, J., “Better differential approximation for symmetric TSP”, Cahier du LAMSADE 261, LAMSADE, Université Paris-Dauphine, 2007.
Escoffier, B., and Paschos, V.Th., “Completeness in approximation classes beyond APX”, Theoret. Comput. Sci., 359 (1-3) (2006) 369-377.
Escoffier, B., and Paschos, V.Th., “A survey on the structure of approximation classes”, Cahier du LAMSADE 267, LAMSADE, Université Paris-Dauphine, 2007. Available at http://www.lamsade.dauphine.fr.
Fagin, R., “Generalized first-order spectra and polynomial-time recognizable sets”, in: R.M. Karp, (ed), Complexity of Computations, American Mathematics Society, 1974, 43-73.
Feige, U., and Kilian, J., “Zero knowledge and the chromatic number”, in: Proc. Conference on Computational Complexity, 1996, 278-287.
Garey, M.R., and Johnson, D.S., Computers and Intractability. A Guide to the Theory of NP-completeness, W.H. Freeman, San Francisco, 1979.
Goldsmidt, O., Hochbaum, D.S., and Yu, G., “A modified greedy heuristic for the set covering problem with improved worst case bound”, Inform. Process. Lett., 48 (1993) 305-310.
Grötschel, M., Lovász, L., and Schrijver, A., “The ellipsoid method and its consequences in combinatorial optimization”, Combinatorica, 1 (1981) 169-197.
Halldórsson, M.M., “A still better performance guarantee for approximate graph coloring”, Inform. Process. Lett., 45 (1) (1993) 19-23.
Halldórsson, M.M., “Approximations of weighted independent set and hereditary subset problems”, J. Graph Algorithms Appli., 4 (1) (2000) 1-16.
Halperin, E., “Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs”, in: Proc. Symposium on Discrete Algorithms, SODA'00, 2000.
Hassin, R., and Lahav, S., “Maximizing the number of unused colors in the vertex coloring problem”, Inform. Process. Lett., 52 (1994) 87-90.
Håstad, J., “Clique is hard to approximate within n^(1 - ε)”, Acta Mathematica, 182 (1999) 105-142.
Hochbaum, D.S., “Efficient bounds for the stable set, vertex cover and set packing problems”, Discrete Appl. Math., 6 (1983) 243-254.
Hochbaum, D.S., (ed), Approximation Algorithms for NP-hard Problems, PWS, Boston, 1997.
Ibarra, O.H., and Kim, C.E., “Fast approximation algorithms for the knapsack and sum of subset problems”, J. Assoc. Comput. Mach., 22 (4) (1975) 463-468.
Johnson, D.S., “Approximation algorithms for combinatorial problems”, J. Comput. System Sci., 9 (1974) 256-278.
Karp, R.M., “Reducibility among combinatorial problems”, in: Miller, R.E., and Thatcher, J.W., (eds), Complexity of Computer Computations, Plenum Press, New York, 1972, 85-103.
Khachian, L.G., “A polynomial algorithm for linear programming”, Dokladi Akademiy Nauk SSSR, 224 (1974) 256-278.
Khanna, S., Motwani, R., Sudan, M., and Vazirani, U., “On syntactic versus computational views of approximability”, SIAM J. Comput., 28 (1998) 164-191.
Khot, S., and Regev, O., “Vertex cover might be hard to approximate to within 2 - ε”, in: Proc. Annual Conference on Computational Complexity, CCC'03, 2003, 379-386.
Kleene, S.C., Introduction to Metamathematics, Van Nostrand, Princeton, NJ, 1952.
Lovász, L., “On the ratio of optimal integral and fractional covers”, Discrete Math., 13 (1975) 383-390.
Lovász, L., “Three short proofs in graph theory”, J. Combin. Theory Ser. B, 19 (1975) 269-271.
Monien, B., and Speckenmeyer, E., “Ramsey numbers and an approximation algorithm for the vertex cover problem”, Acta Informatica, 22 (1985) 115-123.
Monnot, J., Paschos, V.Th., and Toulouse, S., “Differential approximation results for the traveling salesman problem with distances 1 and 2”, European J. Oper. Res., 145 (3) (2002) 557-568.
Monnot, J., Paschos, V.Th., and Toulouse, S., “Approximation algorithms for the traveling salesman problem”, Mathematical Methods of Operations Research, 57 (1) (2003) 387-405.
Nemhauser, G.L., and Trotter, L.E., “Vertex packings: structural properties and algorithms”, Math. Programming, 8 (1975) 232-248.
Orponen, P., and Mannila, H., “On approximation preserving reductions: complete problems and robust measures”, Technical Report C-1987-28, Dept. of Computer Science, University of Helsinki, Finland, 1987.
Papadimitriou, C.H., Computational Complexity, Addison-Wesley, 1994.
Papadimitriou, C.H., Το χαμόγελο του Turing (Turing's Smile), Νέα Σύνορα, Athens, 2000. In Greek. English title: Turing.
Papadimitriou, C.H., and Steiglitz, K., Combinatorial Optimization: Algorithms and Complexity, Prentice Hall, New Jersey, 1981.
Papadimitriou, C.H., and Yannakakis, M., “Optimization, approximation and complexity classes”, J. Comput. System Sci., 43 (1991) 425-440.
Paschos, V.Th., “A note on the improvement of the maximum independent set's approximation ratio”, Yugoslav Journal of Operations Research, 5 (1) (1995) 21-26.
Paschos, V.Th., “A survey about how optimal solutions to some covering and packing problems can be approximated”, ACM Comput. Surveys, 29 (2) (1997) 171-209.
Paschos, V.Th., “Polynomial approximation and graph coloring”, Computing, 70 (2003) 41-86.
Paschos, V.Th., Complexité et Approximation Polynomiale, Hermès, Paris, 2004.
Raz, R., and Safra, S., “A sub-constant error probability low-degree test and a sub-constant error probability PCP characterization of NP”, in: Proc. STOC'97, 1997, 475-484.
Sahni, S., and Gonzalez, T., “P-complete approximation problems”, J. Assoc. Comput. Mach., 23 (1976) 555-565.
Schrijver, A., Theory of Linear and Integer Programming, John Wiley & Sons, New York, 1986.
Simon, H.U., “On approximate solutions for combinatorial optimization problems”, SIAM J. Disc. Math., 3 (2) (1990) 294-310.
Slavk, P., “A tight analysis of the greedy algorithm for set cover”, in: Proc. STOC'96, 1996, 435-441.
Vazirani, V., Approximation Algorithms, Springer, Berlin, 2001.
Downloads
Published
Issue
Section
License
Copyright (c) 2009 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
