A hierarchy that does not collapse : alternations in low level space
Page 1
Viliam Geffert (1994)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Birman, Joan S., Hirsch, Michael D. (1998)
Geometry & Topology
Orevkov, V.P. (2004)
Zapiski Nauchnykh Seminarov POMI
F. Cucker, J. L. Montaña, L. M. Pardo (1993)
Extracta Mathematicae
Ker-I Ko (1990)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Russell, Alexander, Sundaram, Ravi (1998)
The Electronic Journal of Combinatorics [electronic only]
Meer, Klaus, Michaux, Christian (1997)
Bulletin of the Belgian Mathematical Society - Simon Stevin
Bürgisser, Peter, Clausen, Michael (1996)
Séminaire Lotharingien de Combinatoire [electronic only]
Bürgisser, Peter (1996)
Séminaire Lotharingien de Combinatoire [electronic only]
Clausen, Michael (1996)
Séminaire Lotharingien de Combinatoire [electronic only]
Marc Demange, Vangelis Paschos (2002)
RAIRO - Operations Research - Recherche Opérationnelle
The main objective of the polynomial approximation is the development of polynomial time algorithms for NP-hard problems, these algorithms guaranteeing feasible solutions lying “as near as possible” to the optimal ones. This work is the fist part of a couple of papers where we introduce the key-concepts of the polynomial approximation and present the main lines of a new formalism. Our purposes are, on the one hand, to present this theory and its objectives and, on the other hand, to discuss the...
Marc Demange, Vangelis Paschos (2002)
RAIRO - Operations Research - Recherche Opérationnelle
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...
Marc Demange, Vangelis Paschos (2010)
RAIRO - Operations Research
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...
Marc Demange, Vangelis Paschos (2010)
RAIRO - Operations Research
Cet article est le premier d'une série de deux articles où nous présentons les principales caractéristiques d'un nouveau formalisme pour l'approximation polynomiale (algorithmique polynomiale à garanties de performances pour les problèmes NP-difficiles). Ce travail est l'occasion d'un regard critique sur ce domaine et de discussions sur la pertinence des notions usuelles. Il est aussi l'occasion de se familiariser avec l'approximation polynomiale, de comprendre ses enjeux et ses méthodes. Ces deux...
Page 1