Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances
DOI10.1051/ro:2003009zbMath1096.68783OpenAlexW2078792212MaRDI QIDQ4457892
Marc Demange, Vangelis Th. Paschos
Publication date: 17 March 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_4_311_0
Analysis of algorithms and problem complexity (68Q25) Convex programming (90C25) Abstract computational complexity for mathematical programming problems (90C60) Approximation methods and heuristics in mathematical programming (90C59) 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 (1)
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
- Approximation algorithms for the TSP with sharpened triangle inequality
- Approximate solution of NP optimization problems
- Approximating the minimum maximal independence number
- Structure preserving reductions among convex optimization problems
- Non deterministic polynomial optimization problems and their approximations
- Optimization, approximation, and complexity classes
- Approximating maximum independent sets by excluding subgraphs
- Approximation algorithms for combinatorial problems
- Differential approximation algorithms for some combinatorial optimization problems
- Zero knowledge and the chromatic number
- Approximating the independence number via the \(\vartheta\)-function
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Bridging gap between standard and differential polynomial approximation: The case of bin-packing
- On Approximate Solutions for Combinatorial Optimization Problems
- Approximate graph coloring by semidefinite programming
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- An analysis of approximations for maximizing submodular set functions—I
- On Syntactic versus Computational Views of Approximability
- Structure in Approximation Classes
- Improved Lower Bounds on the Approximability of the Traveling Salesman Problem
- Performance Guarantees for Approximation Algorithms Depending on Parametrized Triangle Inequalities
- Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : formalisme unifié et classes d'approximation
This page was built for publication: Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances
