Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances
DOI10.1051/RO:2003009zbMATH Open1096.68783OpenAlexW2078792212MaRDI QIDQ4457892FDOQ4457892
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
Recommendations
- Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : formalisme unifié et classes d'approximation
- An introduction to the analysis of approximation algorithms
- On Approximation Algorithms for # P
- Fixed-Parameter and Approximation Algorithms: A New Look
- scientific article
- Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
- New results on the mathematical foundations of asymptotic complexity analysis of algorithms via complexity spaces
- Towards hardness of approximation for polynomial time problems
- scientific article; zbMATH DE number 1263204
- scientific article; zbMATH DE number 597806
Convex programming (90C25) Approximation methods and heuristics in mathematical programming (90C59) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Abstract computational complexity for mathematical programming problems (90C60) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Approximation algorithms for combinatorial problems
- Title not available (Why is that?)
- Optimization, approximation, and complexity classes
- Title not available (Why is that?)
- Approximate graph coloring by semidefinite programming
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Approximating the minimum maximal independence number
- Structure preserving reductions among convex optimization problems
- Differential approximation algorithms for some combinatorial optimization problems
- Title not available (Why is that?)
- Structure in Approximation Classes
- An analysis of approximations for maximizing submodular set functions—I
- Title not available (Why is that?)
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- Bridging gap between standard and differential polynomial approximation: The case of bin-packing
- Approximation algorithms for the TSP with sharpened triangle inequality
- Title not available (Why is that?)
- Title not available (Why is that?)
- Improved Lower Bounds on the Approximability of the Traveling Salesman Problem
- Performance Guarantees for Approximation Algorithms Depending on Parametrized Triangle Inequalities
- Title not available (Why is that?)
- Approximate solution of NP optimization problems
- Zero knowledge and the chromatic number
- Title not available (Why is that?)
- Approximating the independence number via the \(\vartheta\)-function
- Approximating maximum independent sets by excluding subgraphs
- On Syntactic versus Computational Views of Approximability
- Non deterministic polynomial optimization problems and their approximations
- On Approximate Solutions for Combinatorial Optimization Problems
- Title not available (Why is that?)
- Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : formalisme unifié et classes d'approximation
- Title not available (Why is that?)
Cited In (3)
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
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4457892)
