Valeurs extrémales d'un problème d'optimisation combinatoire et approximation polynomiale

Demange, Marc ; Paschos, Vangelis Th.

Mathématiques et Sciences humaines, Tome 136 (1996), p. 51-66 / Harvested from Numdam

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.

Abstract

As a subsequence of some of our previous works on complexity and polynomial approximation theory, we present some further reflections and arguments about extreml, optimal and worst, values (and solutions) of combinatorial optimization problems. This discussion leads us to consider a constant source of contradictions in complexity theory, the timits between constructibility and non-constructibility. In fact, complexity theory, in its current form, is founded on non-constructibility while, two of the main of its topics, the combinatorial optimization and the polynomial approximation theory need both a conceptual framework founded on constructibility. Approximation theory today goes beyond its framework of origin (a set of tools for finding fast solutions for NP-complete problems) since it strongly intervenes in the definition of new mathematical notions and objects making entirely part of the “arsenal” of cotmplexity and it constitutes a major theoretical tool as well for understanding, deepening and enriching complexity theory as for better apprehending class NP. This recent “problemshift” for the polynomial approximation theory brings to the fore new and particularly interesting problemsfrom both mathematical and epistemological points of view.

Détail

Publié le : 1996-01-01

MR 1435452 | Zbl 0885.90093

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., Paschos V. 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., Paschos V. 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., Paschos V. 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.