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

Demange, Marc; Paschos, Vangelis Th.

Mathématiques informatique et sciences humaines, Tome 135 (1996), pp. 51-66.

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.

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.

[1] Arora S., Lund C., Motwani R., Sudan M., Szegedy M., "proof verification and intractability of approximation problems" , Proc. FOCS (1992), 14-23. | Zbl

[2] Aspvall B., Stone R.E., "Khachiyan's linear programming algorithm ", J. Algorithms, 1 (1980), 1-13. | MR | Zbl

[3] Ausiello G., D'Atri A., Protasi M., "structure preserving reductions among convex optimization problems", J. Comput. System Sci., 21 (1980), 136-153. | MR | Zbl

[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

[5] Berge C., graphs and hypergraphs, Amsterdam, North Holland, 1973. | MR | Zbl

[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 | Zbl

[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

[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

[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 | Zbl

[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 | Zbl

[14] Lund C., Yannakakis M., "on the hardness of approximating minimization problems", preprint AT&T Bell Laboratories (1992). | MR

[15] Vavasis S.A., "approximation algorithms for indefinite quadratic programming", Math. Programming, 57 (1992), 279-311. | MR | Zbl

[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.