Hostname: page-component-cd9895bd7-jkksz Total loading time: 0 Render date: 2024-12-25T17:38:46.806Z Has data issue: false hasContentIssue false
  • English
  • Français

Autour de nouvelles notions pour l'analyse desalgorithmes d'approximation : de la structure de NPO à la structuredes instances

Published online by Cambridge University Press:  15 July 2003

Marc Demange  and
Vangelis Paschos
Marc Demange
Affiliation:
ESSEC, Cergy-Pontoise, France; [email protected].
Vangelis Paschos
Affiliation:
LAMSADE, Université Paris-Dauphine, France; [email protected].
Get access

Abstract

This paper is the continuation of the paper “Autour de nouvelles notions pour l'analyse desalgorithmes d'approximation: Formalisme unifié et classesd'approximation” where a new formalism for polynomialapproximation and its basic tools allowing an “absolute”(individual) evaluation the approximability properties ofNP-hard problems have been presented and discussed. Inorder to be used for exhibiting a structure for theclass NPO (the optimization problems of NP),these tools must be enriched with an “instrument” allowingcomparisons between approximability properties of differentproblems (these comparisons must be independent on any specificapproximation result of the problems concerned). This instrumentis the approximability-preserving reductions. We show how tointegrate them in the formalism presented and propose thedefinition of a new reduction unifying, under a specific point ofview a great number of existing ones. This new reduction allowsalso to widen the use of the reductions, restricted until noweither between versions of a problem, or between problems, inorder to enhance structural relations between frameworks. Theyallow, for example, to study how standard-approximation propertiesof a problem transform into differential-approximation ones (forthe same problem, or for another one). Finally, we apply theseveral concepts introduced to the study of the structure (andhardness) of the instances of a problem. This point of view seemsparticurarly fruitful for a better apprehension of the hardness ofcertain problems and of the mechanisms for the design of efficientsolutions for them.

Keywords

Complexitédifficulté intrinsèqueanalyse des algorithmes et des problèmesalgorithmes d'approximation
Type
Research Article
Information
RAIRO - Operations Research , Volume 36 , Issue 4 , October 2002 , pp. 311 - 350
Copyright
© EDP Sciences, 2002

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

L. Alfandari, Approximation de problèmes de couverture et de partitionnement de graphes, Ph.D. Thesis. LAMSADE, Université Paris-Dauphine (1999).
N. Alon et N. Kahale, Approximating the independence number via the θ-function. Math. Programming (1998).
Andreæ, T. et Bandelt, H.-J., Performance guarantees for approximation algorithms depending on parametrized triangle inequalities. SIAM J. Discrete Math. 8 (1995) 1-16. CrossRef
G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela et M. Protasi, Complexity and approximation. Combinatorial optimization problems and their approximability properties. Springer, Heidelberg (1999).
Ausiello, G., Crescenzi, P. et Protasi, M., Approximate solutions of NP optimization problems. Theoret. Comput. Sci. 150 (1995) 1-55. CrossRef
Ausiello, G., D'Atri, A. et Protasi, M., Structure preserving reductions among convex optimization problems. J. Comput. System Sci. 21 (1980) 136-153. CrossRef
M.A. Bender et C. Chekuri, Performance guarantees for the TSP with a parametrized triangle inequality, dans Proc. WADS'99. Springer, Lecture Notes in Comput. Sci. 1663 (1999) 80-85.
C. Berge, Graphs and hypergraphs. North Holland, Amsterdam (1973).
Berman, P. et Hartmanis, J., On isomorphisms and density of np and other complete sets. SIAM J. Comput. 6 (1977) 305-322. CrossRef
H.-J. Böckenhauer, J. Hromkovic, R. Klasing, S. Seibert et W. Unger, Towards the notion of stability of approximation algorithms and the traveling salesman problem, Report 31, Electr. Colloq. Computational Comp. (1999).
height 2pt depth -1.6pt width 23pt, Approximation, algorithms for the TSP with sharpened triangle inequality. Inform. Process. Lett. 75 (2000) 133-138.
height 2pt depth -1.6pt width 23pt, An improved lower bound on the approximability of metric TSP and approximation algorithms for the TSP with sharpened triangle inequality, dans Proc. STACS'00. Springer, Lecture Notes in Comput. Sci. (2000) 382-394.
Böckenhauer, H.-J. et Seibert, S., Improved lower bounds on the approximability of the traveling salesman problem. RAIRO: Theoret. Informatics Appl. 34 (2000) 213-255.
Boppana, B.B. et Halldórsson, M.M., Approximating maximum independent sets by excluding subgraphs. BIT 32 (1992) 180-196. CrossRef
N. Creignou, Temps linéaire et problèmes NP-complets, Ph.D. Thesis. Université de Caen (1993).
P. Crescenzi, A short guide to approximation preserving reductions, dans Proc. Conference on Computational Complexity (1997) 262-273.
P. Crescenzi, V. Kann, R. Silvestri et L. Trevisan, Structure in approximation classes, Technical Report TR96-066, Electronic Colloquium on Computational Complexity (1996). Available on www_address: http://www.eccc.uni-trier.de/eccc/
P. CRESCENZI ET A. PANCONESI, Completeness in approximation classes. SIAM J. Comput. (1991).
Demange, M., Grisoni, P. et Paschos, V.T., Differential approximation algorithms for some combinatorial optimization problems. Theoret. Comput. Sci. 209 (1998) 107-122. CrossRef
Demange, M., Monnot, J. et Paschos, V.T., Bridging gap between standard and differential polynomial approximation: The case of bin-packing. Appl. Math. Lett. 12 (1999) 127-133. CrossRef
height 2pt depth -1.6pt width 23pt, Maximizing, the number of unused bins. Found. Comput. Decision Sci. 26 (2001) 169-186.
Demange, M. et Paschos, V.T., Valeurs extrémales d'un problème d'optimisation combinatoire et approximation polynomiale. Math. Inf. Sci. Humaines 135 (1996) 51-66.
height 2pt depth -1.6pt width 23pt, Towards a general formal framework for polynomial approximation. Cahier du LAMSADE 177. LAMSADE, Université Paris-Dauphine (2001).
height 2pt depth -1.6pt width 23pt, Autour de, nouvelles notions pour l'analyse des algorithmes d'approximation : formalisme unifié et classes d'approximation. RAIRO: Oper. Res. 36 (2002) 237-277.
U. Feige et J. Kilian, Zero knowledge and the chromatic number, dans Proc. Conference on Computational Complexity (1996) 278-287.
M.R. Garey et D.S. Johnson, Computers and intractability. A guide to the theory of NP-completeness. W. H. Freeman, San Francisco (1979).
Halldórsson, M.M., Approximating the minimum maximal independence number. Inform. Process. Lett. 46 (1993) 169-172. CrossRef
height 2pt depth -1.6pt width 23pt, Approximations via partitioning, JAIST Research Report IS-RR-95-0003F. Japan Advanced Institute of Science and Technology, Japan (1995).
Håstad, J., Clique is hard to approximate within n1-ε . Acta Math. 182 (1999) 105-142. CrossRef
D.S. Hochbaum, Approximation algorithms for NP-hard problems. PWS, Boston (1997).
Johnson, D.S., Approximation algorithms for combinatorial problems. J. Comput. System Sci. 9 (1974) 256-278. CrossRef
Kann, V., Polynomially bounded problems that are hard to approximate. Nordic J. Comput. 1 (1994) 317-331.
Karger, D., Motwani, R. et Sudan, M., Approximate graph coloring by semidefinite programming. J. Assoc. Comput. Mach. 45 (1998) 246-265. CrossRef
R.M. Karp, Reducibility among combinatorial problems, dans Complexity of computer computations, édité par R.E. Miller et J.W. Thatcher, Plenum Press, New York (1972) 85-103.
Khanna, S., Motwani, R., Sudan, M. et Vazirani, U., On syntactic versus computational views of approximability. SIAM J. Comput. 28 (1998) 164-191. CrossRef
J. Lorenzo, Approximation des solutions et des valeurs des problèmes NP-complets, Thèse de Doctorat. CERMSEM, Université Paris I (en préparation).
Lynch, N. et Lipton, J., On structure preserving reductions. SIAM J. Comput. 7 (1978) 119-126. CrossRef
J. Monnot, Familles critiques d'instances et approximation polynomiale, Ph.D. Thesis. LAMSADE, Université Paris-Dauphine (1998).
Nemhauser, G.L., Wolsey, L.A. et Fischer, M.L., An analysis of approximations for maximizing submodular set functions. Math. Programming 14 (1978) 265-294. CrossRef
P. Orponen et H. Mannila, On approximation preserving reductions: Complete problems and robust measures, Tech. Rep. C-1987-28. Dept. of Computer Science, University of Helsinki, Finland (1987).
C.H. Papadimitriou et K. Steiglitz, Combinatorial optimization: Algorithms and complexity. Prentice Hall, New Jersey (1981).
Papadimitriou, C.H. et Yannakakis, M., Optimization, approximation and complexity classes. J. Comput. System Sci. 43 (1991) 425-440. CrossRef
Paz, A. et Moran, S., Non deterministic polynomial optimization problems and their approximations. Theoret. Comput. Sci. 15 (1981) 251-277. CrossRef
Simon, H.U., On approximate solutions for combinatorial optimization problems. SIAM J. Discrete Math. 3 (1990) 294-310. CrossRef
V. Vazirani, Approximation algorithms. Springer, Heidelberg (2001).