Recherche et téléchargement d’archives de revues mathématiques numérisées

 
 
  Table des matières de ce fascicule | Article précédent
Demange, Marc; Paschos, Vangelis Th.
Valeurs extrémales d'un problème d'optimisation combinatoire et approximation polynomiale. Mathématiques et Sciences Humaines, 135 (1996), p. 51-66
Texte intégral djvu | pdf | Analyses MR 1435452 | Zbl 0885.90093 | 3 citations dans Numdam

URL stable: http://www.numdam.org/item?id=MSH_1996__135__51_0

Résumé

A la suite de quelques-uns de nos travaux antérieurs sur la théorie de la complexité et de l'approximation polynomiale, nous présentons quelques nouvelles réflexions et arguments sur les valeurs (et solutions) extrérmales, (optimale et pire), des problèmes d'optirnisation combinatoire. Cette discussion nous conduit à considérer la limite entre constructibilité et non-constructibilité, source constante de contradiction en théorie de la complexité. En effet, cette théorie, telle qu'on la connaît et manie aujourd'hui, est fondée sur la non-constructibilité tandis que deux de ses domaines principaux, l'optimisation combinatoire et la théorie de l'approximation polynomiale, nécessitent un cadre conceptuel fondé sur la constructibilité. L'approximation polynomiale dépasse aujourd'hui sa conception originelle (en tant qu'ensemble d'outils pour la résolution rapide des problèmes NP-complets), intervient très fortement dans la définition de nouvelles notions et objets mathématiques et fait ainsi partie à part entière de «l'arsenal» de la complexité. Elle est un outil théorique majeur pour l'appréhension, l'approfondissement et l'enrichissement de la théorie de la complexité et notamment de la connaissance de la classe NP. Ces développements récents de d'approximation polynomiale dévoilent des problèmes particulièrement inténessants, notamment d'un point de vue épistémologique.

Bibliographie

[1] Arora S., Lund C., Motwani R., Sudan M., Szegedy M., " proof verification and intractability of approximation problems" , Proc. FOCS (1992), 14-23.  Zbl 0977.68539
[2] Aspvall B., Stone R.E., " Khachiyan's linear programming algorithm ", J. Algorithms, 1 (1980), 1-13.  MR 578074 |  Zbl 0438.90053
[3] Ausiello G., D'Atri A., Protasi M., " structure preserving reductions among convex optimization problems", J. Comput. System Sci., 21 (1980), 136-153.  MR 589808 |  Zbl 0441.68049
[4] Ausiello G., Crescenzi P., Protasi M., " approximate solutions of NP optimization problems" Technical Report SI/RR-94/03 (1994), Università di Roma " La Sapienza" .  MR 1357119
[5] Berge C., graphs and hypergraphs, Amsterdam, North Holland, 1973.  MR 357172 |  Zbl 0254.05101
[6] Bourjolly J. - M., Hammer P.L., Simeone B., " node-weighted graphs having the König-Egervary property", Math. Prog. Study, 22 (1984), 44-63.  MR 774233 |  Zbl 0558.05054
[7] Demange M., approximation polynomiale de problèmes NP-complets et programmation linéaire: une nouvelle mesure d'approximation et algorithmes, thèse de Doctorat, Université Paris I, 1994.
[8] Demange M., Grisoni P., Paschos V. Th., " differential approximation algorithms for some combinatorial optimization problems", Cahier Eco & Maths, 94.65 (1994), Université Paris I.
[9] Demange M., PaschosV. Th., " on an approximation measure founded on the links between optimization and polynomial approximation theory", Theoretical Comp. Sci., à à paraître.  Zbl 0871.90069
[10] Demange M., PaschosV. Th., " the approximability behaviour of some combinatorial problems with respect to the approximability of a class of maximum independent set problems", Computational Optimization and Applications, à paraître.  Zbl 0872.90106
[11] Demange M., PaschosV. Th., " exact and approximation results on maximum independent set and minimum vertex covering - graphs with great stability number" , Cahier Eco & Maths, 94.68 (1994), Université Paris I.
[12] R.W. Deming, " Independence Numbers of Graphs - An Extension of the König-Egervary Theorem",Discrete Maths 27, pp. 23-33, 1979.  MR 534950 |  Zbl 0404.05034
[13] Garey M.R., Johnson D.S., computers and intractability : a guide to the theory of NP-completeness, San Francisco, Freeman and Company, 1979.  MR 519066 |  Zbl 0411.68039
[14] Lund C., Yannakakis M., " on the hardness of approximating minimization problems", preprint AT&T Bell Laboratories (1992).  MR 1371491
[15] Vavasis S.A., " approximation algorithms for indefinite quadratic programming", Math. Programming, 57 (1992), 279-311.  MR 1195028 |  Zbl 0845.90095
[16] Zemel E., " functions for measuring the quality of approximate solutions to zero-one programming problems" Discussion Paper (1978), Graduate School of Management, North-western University, Evanston, Illinois.
Copyright Cellule MathDoc 2014 | Crédit | Plan du site