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

Marc Demange; Vangelis Th. Paschos

Mathématiques et Sciences Humaines (1996)

  • Volume: 135, page 51-66
  • ISSN: 0987-6936

Abstract

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

How to cite

top

Demange, Marc, and Paschos, Vangelis Th.. "Valeurs extrémales d'un problème d'optimisation combinatoire et approximation polynomiale." Mathématiques et Sciences Humaines 135 (1996): 51-66. <http://eudml.org/doc/94486>.

@article{Demange1996,
abstract = {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.},
author = {Demange, Marc, Paschos, Vangelis Th.},
journal = {Mathématiques et Sciences Humaines},
keywords = {combinatorial optimization; contradictions in complexity theory; constructibility; polynomial approximation},
language = {fre},
pages = {51-66},
publisher = {Ecole des hautes-études en sciences sociales},
title = {Valeurs extrémales d'un problème d'optimisation combinatoire et approximation polynomiale},
url = {http://eudml.org/doc/94486},
volume = {135},
year = {1996},
}

TY - JOUR
AU - Demange, Marc
AU - Paschos, Vangelis Th.
TI - Valeurs extrémales d'un problème d'optimisation combinatoire et approximation polynomiale
JO - Mathématiques et Sciences Humaines
PY - 1996
PB - Ecole des hautes-études en sciences sociales
VL - 135
SP - 51
EP - 66
AB - 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.
LA - fre
KW - combinatorial optimization; contradictions in complexity theory; constructibility; polynomial approximation
UR - http://eudml.org/doc/94486
ER -

References

top
  1. [1] Arora S., Lund C., Motwani R., Sudan M., Szegedy M., "proof verification and intractability of approximation problems" , Proc. FOCS (1992), 14-23. Zbl0977.68539
  2. [2] Aspvall B., Stone R.E., "Khachiyan's linear programming algorithm ", J. Algorithms, 1 (1980), 1-13. Zbl0438.90053MR578074
  3. [3] Ausiello G., D'Atri A., Protasi M., "structure preserving reductions among convex optimization problems", J. Comput. System Sci., 21 (1980), 136-153. Zbl0441.68049MR589808
  4. [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" . Zbl0874.68145MR1357119
  5. [5] Berge C., graphs and hypergraphs, Amsterdam, North Holland, 1973. Zbl0254.05101MR357172
  6. [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. Zbl0558.05054MR774233
  7. [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. [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. Zbl0912.68061
  9. [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. Zbl0871.90069
  10. [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. Zbl0872.90106
  11. [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. [12] R.W. Deming, "Independence Numbers of Graphs - An Extension of the König-Egervary Theorem",Discrete Maths27, pp. 23-33, 1979. Zbl0404.05034MR534950
  13. [13] Garey M.R., Johnson D.S., computers and intractability : a guide to the theory of NP-completeness, San Francisco, Freeman and Company, 1979. Zbl0411.68039MR519066
  14. [14] Lund C., Yannakakis M., "on the hardness of approximating minimization problems", preprint AT&T Bell Laboratories (1992). Zbl1310.68094MR1371491
  15. [15] Vavasis S.A., "approximation algorithms for indefinite quadratic programming", Math. Programming, 57 (1992), 279-311. Zbl0845.90095MR1195028
  16. [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. 

Citations in EuDML Documents

top
  1. Marc Demange, Vangelis Th. Paschos, Asymptotic differential approximation ratio : definitions, motivations and application to some combinatorial problems
  2. Marc Demange, Vangelis Paschos, Autour de nouvelles notions pour l’analyse des algorithmes d’approximation : formalisme unifié et classes d’approximation
  3. Marc Demange, Vangelis Paschos, Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances
  4. Marc Demange, Vangelis Paschos, Autour de nouvelles notions pour l’analyse des algorithmes d’approximation : de la structure de NPO à la structure des instances

NotesEmbed ?

top

You must be logged in to post comments.