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

Marc Demange; Vangelis Paschos

RAIRO - Operations Research (2010)

  • Volume: 36, Issue: 4, page 311-350
  • ISSN: 0399-0559

Abstract

top
This paper is the continuation of the paper “Autour de nouvelles notions pour l'analyse des algorithmes d'approximation: Formalisme unifié et classes d'approximation” where a new formalism for polynomial approximation and its basic tools allowing an “absolute” (individual) evaluation the approximability properties of NP-hard problems have been presented and discussed. In order to be used for exhibiting a structure for the class NPO (the optimization problems of NP), these tools must be enriched with an “instrument” allowing comparisons between approximability properties of different problems (these comparisons must be independent on any specific approximation result of the problems concerned). This instrument is the approximability-preserving reductions. We show how to integrate them in the formalism presented and propose the definition of a new reduction unifying, under a specific point of view a great number of existing ones. This new reduction allows also to widen the use of the reductions, restricted until now either between versions of a problem, or between problems, in order to enhance structural relations between frameworks. They allow, for example, to study how standard-approximation properties of a problem transform into differential-approximation ones (for the same problem, or for another one). Finally, we apply the several concepts introduced to the study of the structure (and hardness) of the instances of a problem. This point of view seems particurarly fruitful for a better apprehension of the hardness of certain problems and of the mechanisms for the design of efficient solutions for them.

How to cite

top

Demange, Marc, and Paschos, Vangelis. "Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances." RAIRO - Operations Research 36.4 (2010): 311-350. <http://eudml.org/doc/105276>.

@article{Demange2010,
abstract = { This paper is the continuation of the paper “Autour de nouvelles notions pour l'analyse des algorithmes d'approximation: Formalisme unifié et classes d'approximation” where a new formalism for polynomial approximation and its basic tools allowing an “absolute” (individual) evaluation the approximability properties of NP-hard problems have been presented and discussed. In order to be used for exhibiting a structure for the class NPO (the optimization problems of NP), these tools must be enriched with an “instrument” allowing comparisons between approximability properties of different problems (these comparisons must be independent on any specific approximation result of the problems concerned). This instrument is the approximability-preserving reductions. We show how to integrate them in the formalism presented and propose the definition of a new reduction unifying, under a specific point of view a great number of existing ones. This new reduction allows also to widen the use of the reductions, restricted until now either between versions of a problem, or between problems, in order to enhance structural relations between frameworks. They allow, for example, to study how standard-approximation properties of a problem transform into differential-approximation ones (for the same problem, or for another one). Finally, we apply the several concepts introduced to the study of the structure (and hardness) of the instances of a problem. This point of view seems particurarly fruitful for a better apprehension of the hardness of certain problems and of the mechanisms for the design of efficient solutions for them. },
author = {Demange, Marc, Paschos, Vangelis},
journal = {RAIRO - Operations Research},
keywords = {Complexité; difficulté intrinsèque; analyse des algorithmes et des problèmes; algorithmes d'approximation},
language = {eng},
month = {3},
number = {4},
pages = {311-350},
publisher = {EDP Sciences},
title = {Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances},
url = {http://eudml.org/doc/105276},
volume = {36},
year = {2010},
}

TY - JOUR
AU - Demange, Marc
AU - Paschos, Vangelis
TI - Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances
JO - RAIRO - Operations Research
DA - 2010/3//
PB - EDP Sciences
VL - 36
IS - 4
SP - 311
EP - 350
AB - This paper is the continuation of the paper “Autour de nouvelles notions pour l'analyse des algorithmes d'approximation: Formalisme unifié et classes d'approximation” where a new formalism for polynomial approximation and its basic tools allowing an “absolute” (individual) evaluation the approximability properties of NP-hard problems have been presented and discussed. In order to be used for exhibiting a structure for the class NPO (the optimization problems of NP), these tools must be enriched with an “instrument” allowing comparisons between approximability properties of different problems (these comparisons must be independent on any specific approximation result of the problems concerned). This instrument is the approximability-preserving reductions. We show how to integrate them in the formalism presented and propose the definition of a new reduction unifying, under a specific point of view a great number of existing ones. This new reduction allows also to widen the use of the reductions, restricted until now either between versions of a problem, or between problems, in order to enhance structural relations between frameworks. They allow, for example, to study how standard-approximation properties of a problem transform into differential-approximation ones (for the same problem, or for another one). Finally, we apply the several concepts introduced to the study of the structure (and hardness) of the instances of a problem. This point of view seems particurarly fruitful for a better apprehension of the hardness of certain problems and of the mechanisms for the design of efficient solutions for them.
LA - eng
KW - Complexité; difficulté intrinsèque; analyse des algorithmes et des problèmes; algorithmes d'approximation
UR - http://eudml.org/doc/105276
ER -

References

top
  1. L. Alfandari, Approximation de problèmes de couverture et de partitionnement de graphes, Ph.D. Thesis. LAMSADE, Université Paris-Dauphine (1999).  
  2. N. Alon et N. Kahale, Approximating the independence number via the θ-function. Math. Programming (1998).  
  3. T. Andreæ et H.-J. Bandelt, Performance guarantees for approximation algorithms depending on parametrized triangle inequalities. SIAM J. Discrete Math.8 (1995) 1-16.  
  4. 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).  
  5. G. Ausiello, P. Crescenzi et M. Protasi, Approximate solutions of NP optimization problems. Theoret. Comput. Sci.150 (1995) 1-55.  
  6. G. Ausiello, A. D'Atri et M. Protasi, Structure preserving reductions among convex optimization problems. J. Comput. System Sci.21 (1980) 136-153.  
  7. 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.  
  8. C. Berge, Graphs and hypergraphs. North Holland, Amsterdam (1973).  
  9. P. Berman et J. Hartmanis, On isomorphisms and density of np and other complete sets. SIAM J. Comput.6 (1977) 305-322.  
  10. 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).  
  11. height 2pt depth -1.6pt width 23pt, Approximation algorithms for the TSP with sharpened triangle inequality. Inform. Process. Lett.75 (2000) 133-138.  
  12. 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.  
  13. H.-J. Böckenhauer et S. Seibert, Improved lower bounds on the approximability of the traveling salesman problem. RAIRO: Theoret. Informatics Appl.34 (2000) 213-255.  
  14. B.B. Boppana et M.M. Halldórsson, Approximating maximum independent sets by excluding subgraphs. BIT32 (1992) 180-196.  
  15. N. Creignou, Temps linéaire et problèmes NP-complets, Ph.D. Thesis. Université de Caen (1993).  
  16. P. Crescenzi, A short guide to approximation preserving reductions, dans Proc. Conference on Computational Complexity (1997) 262-273.  
  17. 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/  
  18. P. CRESCENZI ET A. PANCONESI, Completeness in approximation classes. SIAM J. Comput. (1991).  
  19. M. Demange, P. Grisoni et V.T. Paschos, Differential approximation algorithms for some combinatorial optimization problems. Theoret. Comput. Sci.209 (1998) 107-122.  
  20. M. Demange, J. Monnot et V.T. Paschos, Bridging gap between standard and differential polynomial approximation: The case of bin-packing. Appl. Math. Lett.12 (1999) 127-133.  
  21. height 2pt depth -1.6pt width 23pt, Maximizing the number of unused bins. Found. Comput. Decision Sci.26 (2001) 169-186.  
  22. M. Demange et V.T. Paschos, Valeurs extrémales d'un problème d'optimisation combinatoire et approximation polynomiale. Math. Inf. Sci. Humaines135 (1996) 51-66.  
  23. height 2pt depth -1.6pt width 23pt, Towards a general formal framework for polynomial approximation. Cahier du LAMSADE177. LAMSADE, Université Paris-Dauphine (2001).  
  24. 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.  
  25. U. Feige et J. Kilian, Zero knowledge and the chromatic number, dans Proc. Conference on Computational Complexity (1996) 278-287.  
  26. M.R. Garey et D.S. Johnson, Computers and intractability. A guide to the theory of NP-completeness. W. H. Freeman, San Francisco (1979).  
  27. M.M. Halldórsson, Approximating the minimum maximal independence number. Inform. Process. Lett.46 (1993) 169-172.  
  28. 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).  
  29. J. Håstad, Clique is hard to approximate within n1-ε. Acta Math.182 (1999) 105-142.  
  30. D.S. Hochbaum, Approximation algorithms for NP-hard problems. PWS, Boston (1997).  
  31. D.S. Johnson, Approximation algorithms for combinatorial problems. J. Comput. System Sci.9 (1974) 256-278.  
  32. V. Kann, Polynomially bounded problems that are hard to approximate. Nordic J. Comput.1 (1994) 317-331.  
  33. D. Karger, R. Motwani et M. Sudan, Approximate graph coloring by semidefinite programming. J. Assoc. Comput. Mach.45 (1998) 246-265.  
  34. 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.  
  35. S. Khanna, R. Motwani, M. Sudan et U. Vazirani, On syntactic versus computational views of approximability. SIAM J. Comput.28 (1998) 164-191.  
  36. J. Lorenzo, Approximation des solutions et des valeurs des problèmes NP-complets, Thèse de Doctorat. CERMSEM, Université Paris I (en préparation).  
  37. N. Lynch et J. Lipton, On structure preserving reductions. SIAM J. Comput.7 (1978) 119-126.  
  38. J. Monnot, Familles critiques d'instances et approximation polynomiale, Ph.D. Thesis. LAMSADE, Université Paris-Dauphine (1998).  
  39. G.L. Nemhauser, L.A. Wolsey et M.L. Fischer, An analysis of approximations for maximizing submodular set functions. Math. Programming14 (1978) 265-294.  
  40. 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).  
  41. C.H. Papadimitriou et K. Steiglitz, Combinatorial optimization: Algorithms and complexity. Prentice Hall, New Jersey (1981).  
  42. C.H. Papadimitriou et M. Yannakakis, Optimization, approximation and complexity classes. J. Comput. System Sci.43 (1991) 425-440.  
  43. A. Paz et S. Moran, Non deterministic polynomial optimization problems and their approximations. Theoret. Comput. Sci.15 (1981) 251-277.  
  44. H.U. Simon, On approximate solutions for combinatorial optimization problems. SIAM J. Discrete Math.3 (1990) 294-310.  
  45. V. Vazirani, Approximation algorithms. Springer, Heidelberg (2001).  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.