Studying graph - stability to apprehend relative hardness of constructive-non-constructive approximation
Valeurs extrémales d'un problème d'optimisation combinatoire et approximation polynomiale
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...
Asymptotic differential approximation ratio : definitions, motivations and application to some combinatorial problems
Asymptotic differential approximation ratio: Definitions, motivations and application to some combinatorial problems
We first motivate and define a notion of asymptotic differential approximation ratio. For this, we introduce a new class of problems called radial problems including in particular the hereditary ones. Next, we validate the definition of the asymptotic differential approximation ratio by proving positive, conditional and negative approximation results for some combinatorial problems. We first derive a differential approximation analysis of a classical greedy algorithm for bin packing, the “first...
On-line models and algorithms for max independent set
In on-line computation, the instance of the problem dealt is not entirely known from the beginning of the solution process, but it is revealed step-by-step. In this paper we deal with on-line independent set. On-line models studied until now for this problem suppose that the input graph is initially empty and revealed either vertex-by-vertex, or cluster-by-cluster. Here we present a new on-line model quite different to the ones already studied. It assumes that a superset of the final graph is initially...
A Note on the Improvement of the Maximum Independent Set's Approximation Ratio
An Overview on Polynomial Approximation of NP-Hard Problems
Page 1