Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : formalisme unifié et classes d'approximation
From MaRDI portal
Publication:4809670
DOI10.1051/ro:2003005zbMath1089.68668OpenAlexW1993793260MaRDI QIDQ4809670
Vangelis Th. Paschos, Marc Demange
Publication date: 30 August 2004
Published in: RAIRO - Operations Research (Search for Journal in Brave)
Full work available at URL: http://www.numdam.org/item?id=RO_2002__36_3_237_0
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Scheduling on parallel machines with preemption and transportation delays, Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Greed is good: Approximating independent sets in sparse and bounded-degree graphs
- Efficient bounds for the stable set, vertex cover and set packing problems
- Sur la cardinalite maximum des couplages d'hypergraphes aléatoires uniformes
- Approximating maximum independent sets by excluding subgraphs
- A still better performance guarantee for approximate graph coloring
- Approximation algorithms for combinatorial problems
- Differential approximation algorithms for some combinatorial optimization problems
- Zero knowledge and the chromatic number
- Maximizing the number of unused colors in the vertex coloring problem
- On an approximation measure founded on the links between optimization and polynomial approximation theory
- Improved approximations for maximum independent set via approximation chains
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Bridging gap between standard and differential polynomial approximation: The case of bin-packing
- A Greedy Heuristic for the Set-Covering Problem
- Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
- An analysis of approximations for maximizing submodular set functions—I
- On Syntactic versus Computational Views of Approximability
- On the hardness of approximating minimization problems
- Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances
- The complexity of theorem-proving procedures
