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 - Recherche Opérationnelle (2002)

  • 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 - Recherche Opérationnelle 36.4 (2002): 311-350. <http://eudml.org/doc/245131>.

@article{Demange2002,
abstract = {Cet article est la suite de l’article «Autour de nouvelles notions pour l’analyse des algorithmes d’approximation : formalisme unifié et classes d’approximation» où nous avons présenté et discuté, dans le cadre d’un nouveau formalisme pour l’approximation polynomiale (algorithmique polynomiale à garanties de performances pour des problèmes NP-difficiles), des outils permettant d’évaluer, dans l’absolu, les proporiétés d’approximation de problèmes difficiles. Afin de répondre pleinement à l’objectif de l’approximation polynomiale de mettre en évidence et étudier une structure de la classe NPO (problèmes d’optimisation de NP), ces outils ont besoin d’être complétés pour offrir la possibilité de comparer, indépendamment de tout résultat spécifique, les propriétés d’approximation de problèmes différents. C’est l’objet de la notion de réduction en approximation à laquelle nous nous intéressons ici. Nous montrons comment l’intégrer au nouveau formalisme et présentons une définition qui unifie, sous un point de vue spécifique, les nombreuses notions existantes. Cette définition permet aussi un emploi systématique de réductions pour étudier des liens entre différents problèmes, entre différentes versions d’un problème ou encore entre le cadre de l’approximation classique et celui de l’approximation différentielle. Comme dans l’article «Autour de nouvelles notions pour l’analyse des algorithmes d’approximation : formalisme unifié et classes d’approximation», ce travail est illustré par de nombreux exemples et s’adresse tant aux spécialistes du domaine, pour un débat commun, qu’aux non spécialistes qui ont une occasion de se familiariser avec ce domaine. Enfin, nous appliquons les différents concepts à l’étude de la struture (et la difficulté) des instances d’un problème. Cette problématique s’avère très intéressante pour une meilleure compréhension de la difficulté de certains problèmes et pour leur résolution efficace. Mots Clés. Complexité, difficulté intrinsèque, analyse des algorithmes et des problèmes, algorithmes d’approximation. Classification Mathématique. 68Q15, 68Q17, 68Q25, 68W25.},
author = {Demange, Marc, Paschos, Vangelis},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
language = {fre},
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/245131},
volume = {36},
year = {2002},
}

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 - Recherche Opérationnelle
PY - 2002
PB - EDP-Sciences
VL - 36
IS - 4
SP - 311
EP - 350
AB - Cet article est la suite de l’article «Autour de nouvelles notions pour l’analyse des algorithmes d’approximation : formalisme unifié et classes d’approximation» où nous avons présenté et discuté, dans le cadre d’un nouveau formalisme pour l’approximation polynomiale (algorithmique polynomiale à garanties de performances pour des problèmes NP-difficiles), des outils permettant d’évaluer, dans l’absolu, les proporiétés d’approximation de problèmes difficiles. Afin de répondre pleinement à l’objectif de l’approximation polynomiale de mettre en évidence et étudier une structure de la classe NPO (problèmes d’optimisation de NP), ces outils ont besoin d’être complétés pour offrir la possibilité de comparer, indépendamment de tout résultat spécifique, les propriétés d’approximation de problèmes différents. C’est l’objet de la notion de réduction en approximation à laquelle nous nous intéressons ici. Nous montrons comment l’intégrer au nouveau formalisme et présentons une définition qui unifie, sous un point de vue spécifique, les nombreuses notions existantes. Cette définition permet aussi un emploi systématique de réductions pour étudier des liens entre différents problèmes, entre différentes versions d’un problème ou encore entre le cadre de l’approximation classique et celui de l’approximation différentielle. Comme dans l’article «Autour de nouvelles notions pour l’analyse des algorithmes d’approximation : formalisme unifié et classes d’approximation», ce travail est illustré par de nombreux exemples et s’adresse tant aux spécialistes du domaine, pour un débat commun, qu’aux non spécialistes qui ont une occasion de se familiariser avec ce domaine. Enfin, nous appliquons les différents concepts à l’étude de la struture (et la difficulté) des instances d’un problème. Cette problématique s’avère très intéressante pour une meilleure compréhension de la difficulté de certains problèmes et pour leur résolution efficace. Mots Clés. Complexité, difficulté intrinsèque, analyse des algorithmes et des problèmes, algorithmes d’approximation. Classification Mathématique. 68Q15, 68Q17, 68Q25, 68W25.
LA - fre
UR - http://eudml.org/doc/245131
ER -

References

top
  1. [1] L. Alfandari, Approximation de problèmes de couverture et de partitionnement de graphes, Ph.D. Thesis. LAMSADE, Université Paris-Dauphine (1999). 
  2. [2] N. Alon et N. Kahale, Approximating the independence number via the θ -function. Math. Programming (1998). Zbl0895.90169MR1603356
  3. [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. Zbl0832.90089MR1315955
  4. [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). Zbl0937.68002
  5. [5] G. Ausiello, P. Crescenzi et M. Protasi, Approximate solutions of NP optimization problems. Theoret. Comput. Sci. 150 (1995) 1-55. Zbl0874.68145MR1357119
  6. [6] G. Ausiello, A. D’Atri et M. Protasi, Structure preserving reductions among convex optimization problems. J. Comput. System Sci. 21 (1980) 136-153. Zbl0441.68049
  7. [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. Zbl1063.68700
  8. [8] C. Berge, Graphs and hypergraphs. North Holland, Amsterdam (1973). Zbl0254.05101MR357172
  9. [9] P. Berman et J. Hartmanis, On isomorphisms and density of np and other complete sets. SIAM J. Comput. 6 (1977) 305-322. Zbl0356.68059MR455536
  10. [10] H.-J. Böckenhauer, J. Hromkovič, 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). Zbl1094.90036
  11. [11] , Approximation algorithms for the TSP with sharpened triangle inequality. Inform. Process. Lett. 75 (2000) 133-138. MR1776665
  12. [12] , 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. Zbl1028.90044
  13. [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. Zbl0971.68075MR1796269
  14. [14] B.B. Boppana et M.M. Halldórsson, Approximating maximum independent sets by excluding subgraphs. BIT 32 (1992) 180-196. Zbl0761.68044MR1172185
  15. [15] N. Creignou, Temps linéaire et problèmes NP-complets, Ph.D. Thesis. Université de Caen (1993). 
  16. [16] P. Crescenzi, A short guide to approximation preserving reductions, dans Proc. Conference on Computational Complexity (1997) 262-273. MR1758143
  17. [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/ Zbl0932.68137
  18. [18] P. Crescenzi et A. Panconesi, Completeness in approximation classes. SIAM J. Comput. (1991). Zbl0734.68039MR1115527
  19. [19] M. Demange, P. Grisoni et V.T. Paschos, Differential approximation algorithms for some combinatorial optimization problems. Theoret. Comput. Sci. 209 (1998) 107-122. Zbl0912.68061MR1647498
  20. [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. Zbl0942.68144MR1750071
  21. [21] , Maximizing the number of unused bins. Found. Comput. Decision Sci. 26 (2001) 169-186. Zbl1204.90080MR1843945
  22. [22] M. Demange et V.T. Paschos, Valeurs extrémales d’un problème d’optimisation combinatoire et approximation polynomiale. Math. Inf. Sci. Humaines 135 (1996) 51-66. Zbl0885.90093
  23. [23] , Towards a general formal framework for polynomial approximation. Cahier du LAMSADE 177. LAMSADE, Université Paris-Dauphine (2001). 
  24. [24] , Autour de nouvelles notions pour l’analyse des algorithmes d’approximation : formalisme unifié et classes d’approximation. RAIRO: Oper. Res. 36 (2002) 237-277. Zbl1089.68668
  25. [25] U. Feige et J. Kilian, Zero knowledge and the chromatic number, dans Proc. Conference on Computational Complexity (1996) 278-287. Zbl0921.68089
  26. [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). Zbl0411.68039MR519066
  27. [27] M.M. Halldórsson, Approximating the minimum maximal independence number. Inform. Process. Lett. 46 (1993) 169-172. Zbl0778.68041MR1229204
  28. [28] , Approximations via partitioning, JAIST Research Report IS-RR-95-0003F. Japan Advanced Institute of Science and Technology, Japan (1995). 
  29. [29] J. Håstad, Clique is hard to approximate within n 1 - ϵ . Acta Math. 182 (1999) 105-142. Zbl0989.68060MR1687331
  30. [30] D.S. Hochbaum, Approximation algorithms for NP-hard problems. PWS, Boston (1997). Zbl05899342
  31. [31] D.S. Johnson, Approximation algorithms for combinatorial problems. J. Comput. System Sci. 9 (1974) 256-278. Zbl0296.65036MR449012
  32. [32] V. Kann, Polynomially bounded problems that are hard to approximate. Nordic J. Comput. 1 (1994) 317-331. Zbl0817.68082MR1335251
  33. [33] D. Karger, R. Motwani et M. Sudan, Approximate graph coloring by semidefinite programming. J. Assoc. Comput. Mach. 45 (1998) 246-265. Zbl0904.68116MR1623197
  34. [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. MR378476
  35. [35] S. Khanna, R. Motwani, M. Sudan et U. Vazirani, On syntactic versus computational views of approximability. SIAM J. Comput. 28 (1998) 164-191. Zbl0915.68068MR1630433
  36. [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. [37] N. Lynch et J. Lipton, On structure preserving reductions. SIAM J. Comput. 7 (1978) 119-126. MR502264
  38. [38] J. Monnot, Familles critiques d’instances et approximation polynomiale, Ph.D. Thesis. LAMSADE, Université Paris-Dauphine (1998). 
  39. [39] G.L. Nemhauser, L.A. Wolsey et M.L. Fischer, An analysis of approximations for maximizing submodular set functions. Math. Programming 14 (1978) 265-294. Zbl0374.90045MR503866
  40. [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. [41] C.H. Papadimitriou et K. Steiglitz, Combinatorial optimization: Algorithms and complexity. Prentice Hall, New Jersey (1981). Zbl0503.90060MR663728
  42. [42] C.H. Papadimitriou et M. Yannakakis, Optimization, approximation and complexity classes. J. Comput. System Sci. 43 (1991) 425-440. Zbl0765.68036MR1135471
  43. [43] A. Paz et S. Moran, Non deterministic polynomial optimization problems and their approximations. Theoret. Comput. Sci. 15 (1981) 251-277. Zbl0459.68015MR632398
  44. [44] H.U. Simon, On approximate solutions for combinatorial optimization problems. SIAM J. Discrete Math. 3 (1990) 294-310. Zbl0699.68077MR1039300
  45. [45] V. Vazirani, Approximation algorithms. Springer, Heidelberg (2001). Zbl1005.68002MR1851303

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.