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. (1996) Polynomial time approximation schemes for Euclidean TSP and other geometric problems. u: FOCS'96, Proc, str. 2-11
Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M. (1998) Proof verification and intractability of approximation problems. J. Assoc. Comput. Mach, 45 (3) 501-555
Aspvall, B., Stone, R.E. (1980) Khachiyan's linear programming algorithm. Journal of Algorithms, 1(1): 1
Ausiello, G., Bazgan, C., Demange, M., Paschos, Th.V. (2005) Completeness in differential approximation classes. International Journal of Foundations of Computer Science, 16 (6) 1267-1295
Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M. (1999) Complexity and approximation: Combinatorial optimization problems and their approximability properties. Berlin: Springer-Verlag
Ausiello, G., d'Atri A., Protasi, M. (1980) Structure preserving reductions among convex optimization problems. Journal of Computer and System Sciences, 21(1): 136
Ausiello, G., D'Atri, A., Protasi, M. (1981) Lattice-theoretical ordering properties for NP: Complete optimization problems. Fundamenta Informaticae, 4 83-94
Ausiello, G., Paschos, Th.V. (2006) Reductions, completeness and the hardness of approximability. European Journal of Operational Research, 172(3): 719
Ausiello, G., Paschos, Th.V. (2007) Reductions that preserve approximability. u: Gonzalez T.F. [ur.] Handbook of approximation algorithms, Boca Raton: Chapman & Hall, str. 15-16, and metaheuristics, chapter 15
Bar-Yehuda, R., Even, S. (1985) A local-ratio theorem for approximating the weighted vertex cover problem. Ann. Discrete Appl. Math, 25 27-46
Bazgan, C., Escoffier, B., Paschos, Th.V. (2005) Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness. Theoret. Comput. Sci, 339 272-292
Bazgan, C. (2005) On the differential approximation of MIN SET COVER. Theoretical Computer Science, 332(1-3): 497
Bazgan, C., Paschos, Th.V. (2003) Differential approximation for optimal satisfiability and related problems. European Journal of Operational Research, 147(2): 397
Bell, E.T. (1992) The development of mathematics. Dover
Bellare, M., Goldreich, O., Sudan, M. (1998) Free bits and non-approximability: Towards tight results. SIAM Journal on Computing, 27(3): 804
Berge, C. (1973) Graphs and hypergraphs. Amsterdam, itd: North-Holland
Berman, P., Karpinski, M. (2006) 8/7-approximation algorithm for (1,2)-tsp. u: Symposium on Discrete Algorithms, SODA'06, Proc, 641-648
Brooks, R.L. (1941) On colouring the nodes of a network. Mathematical Proceedings of the Cambridge Philosophical Society, 37(2): 194
Christofides, N. (1976) Worst-case analysis of a new heuristic for the traveling salesman problem. u: Technical report, Grad. School of Industrial Administration, CMU, 338
Chvatal, V. (1979) A greedy-heuristic for the set covering problem. Mathematics of Operations Research, 4(3): 233
Cook, St. (1971) The complexity of theorem proving procedures. u: Proceedings of the third annual ACM symposium on Theory of computing, Shaker Heights, Ohio, str. 151-158
Crescenzi, P. (1997) A short guide to approximation preserving reductions. u: Conference on Computational Complexity, Proc, str. 262-273
Crescenzi, P., Kann, V., Silvestri, R., Trevisan, L. (1999) Structure in approximation classes. SIAM J. Comput, 28 (5) 1759-1782
Crescenzi, P., Panconesi, A. (1991) Completeness in approximation classes. Information and Computation, 93(2) 241-262
Croes, G.A. (1958) A method for solving traveling-salesman problems. Operations Research, 6(6): 791
Demange, M., de Werra, D., Monnot, J., Paschos, V.Th. (2007) Time slot scheduling of compatible jobs. Journal of Scheduling, 10(2): 111
Demange, M., Paschos, V.Th. (1996) On an approximation measure founded on the links between optimization and polynomial approximation theory. Theoretical Computer Science, 158(1-2): 117
Demange, M., Paschos, V.Th. (1997) Improved approximations for maximum independent set via approximation chains. Applied Mathematics Letters, 10(3): 105
Demange, M., Paschos, V.Th. (2005) Improved approximations for weighted and unweighted graph problems. Theory of Computing Systems, 38(6): 763
Escoffier, B., Monnot, J. (2007) Better differential approximation for symmetric TSP. u: Cahier du LAMSADE, 261, LAMSADE, Université Paris-Dauphine
Escoffier, B., Paschos, Th.V. (2006) Completeness in approximation classes beyond APX. Theoret. Comput. Sci, 359 (1-3) 369-377
Escoffier, B., Paschos, Th.V. (2007) A survey on the structure of approximation classes. u: Cahier du LAMSADE, 267, LAMSADE, Université Paris-Dauphine, http://www.lamsade.dauphine.fr
Fagin, R. (1974) Generalized first-order spectra and polynomial-time recognizable sets. u: Karp R.M. [ur.] Complexity of Computations, American Mathematics Society
Feige, U., Kilian, J. (1996) Zero knowledge and the chromatic number. u: Proc Conference on Computational Complexity, str. 278-287
Garey, M.R., Johnson, D.C. (1979) Computer and intractability: A guide to the theory of NP-completeness. San Francisco, CA, itd: W.H. Freeman Publishing
Goldsmidt, O., Hochbaum, D.S., Yu, G. (1993) A modified greedy heuristic for the Set Covering problem with improved worst case bound. Information Processing Letters, 48(6): 305
Grötschel, M., Lovász, L., Schrijver, A. (1981) The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1, 169-197
Halldorsson, M.M. (2000) Approximations of weighted independent set and hereditary subset problems. J Graph Algorithms Appl., 4, 1-
Halldórsson, M.M. (1993) A still better performance guarantee for approximate graph coloring. Information Processing Letters, 45(1): 19
Halperin, E. (2000) Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs. u: Symposium on discrete algorithms, SODA'00, Proceedings
Hassin, R., Lahav, S. (1994) Maximizing the number of unused colors in the vertex coloring problem. Information Processing Letters, 52(2): 87
Hastad, J. (1999) Clique is hard to approximate within $nsp {1-epsilon}$. Acta Math, 182, 1, 105-142
Hochbaum, D.S. (1983) Efficient bounds for the stable set, vertex cover and set packing problems. Discrete Applied Mathematics, 6, 3, 243-254
Hochbaum, D.S., ur. (1997) Approximation algorithms for NP-hard problems. Boston: PWS
Ibarra, O.H., Kim, C.E. (1975) Fast approximation algorithms for the knapsack and sum of subset problems. Journal of the Association for Computing Machinery / JACM, 22, 4, 463-468
Johnson, D.S. (1974) Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences, 9, 256-278
Karp, R.M. (1972) Complexity of computer computations. u: Miller R.E., Thatcher J.W. [ur.] Reducibility Among Combinatorial Problems, New York: Plenum Press, str. 85-103
Khachiyan, L.G. (1979) A polynomial algorithm in linear programming. Dokladi Akademia Nauk SSSR, 244, 5, 1093-1096
Khanna, S., Motwani, R., Sudan, M., Vazirani, U. (1998) On syntactic versus computational views of approximability. SIAM Journal on Computing, 28(1): 164
Khot, S., Regev, O. (2003) Vertex cover might be hard to approximate to within 2-varepsilon. u: Annual Conference on Computational Complexity, CCC'03, Proceedings, str. 379-386
Kleene, S.C. (1952) Introduction to metamathematics. Princeton, NJ: Van Nostrand
Lovasz, L. (1975) Three short proofs in graph theory. Journal of Combinatorial Theory Series B, 19(3): 269
Lovász, L. (1975) On the ratio of optimal integral and fractional covers. Discrete Mathematics, 13(4): 383
Monien, B., Speckenmeyer, E. (1985) Ramsey numbers and an approximation algorithm for the vertex cover problem. Acta Informatica, 22(1): 115
Monnot, J., Paschos, V., Toulouse, S. (2003) Differential approximation results for the traveling salesman problem with distances 1 and 2. European Journal of Operational Research, 145(3): 557
Monnot, J., Paschos, V., Toulouse, S. (2003) Approximation algorithms for the traveling salesman problem. Mathematical Methods of Operations Research, 57 (1) 387-405
Nemhauser, G.L., Trotter, L. (1975) Vertex packings: Structural properties and algorithms. Mathematical Programming Series A, 8, 232-248
Orponen, P., Mannila, H. (1987) On approximation preserving reductions: Complete problems and robust measures'. Helsinki, Finland: University - Dept. of Computer Science, Technical Report C-1987-28
Papadimitriou, C. H. (2000) Το χαμόγελο του Turing / Turing's Smile. Athens: Νέα Σύνορα
Papadimitriou, C.H., Yannakakis, M. (1991) Optimization, approximation, and complexity classes. Journal of Computer and System Sciences, 43(3): 425
Papadimitriou, C.H., Steiglitz, K. (1981) Combinatorial optimization: Algorithm and complexity. Englewood Cliffs, NJ, itd: Prentice Hall
Papadimitriou, H.C. (1994) Computational complexity. San Diego, California: Addison -Wesley Publishing Company
Paschos, V. (2003) Polynomial approximation and graph coloring. Computing, 70 41- 86
Paschos, V.Th. (2004) Complexité et approximation polynomiale. Paris: Hermos
Paschos, V.T. (1997) A survey of approximately optimal solutions to some covering and packing problems. ACM Computing Surveys, 29(2): 171
Paschos, V.Th. (1995) A note on the improvement of the maximum independent set s approximation ratio. Yugoslav Journal of Operations Research, vol. 5, br. 1, str. 21-26
Raz, R., Safra, S. (1997) A sub-constant error probability low-degree test and a sub-constant error probability PCP characterization of NP. u: STOC'97, Proceedings, str. 475-484
Sahni, S., Gonzalez, T. (1976) P-complete approximation problems. J. Assoc. Comput. Mach, 23, 555-565
Schrijver, A. (1986) Theory of linear and integer programming. New York: John Wiley & Sons
Simon, H.U. (1990) On approximate solutions for combinatorial optimization problems. SIAM Journal on Discrete Mathematics, 3(2): 294
Slavk, P. (1996) A tight analysis of the greedy algorithm for set cover. u: STOC'96, Proceedings, 435-441
Vazirani, V. (2001) Approximation algorithms. Berlin: Springer
Downloads
Published
Issue
Section
License
Copyright (c) YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
