Differential approximation algorithms for some combinatorial optimization problems
From MaRDI portal
Publication:1274917
DOI10.1016/S0304-3975(97)00099-6zbMath0912.68061OpenAlexW2089061537MaRDI QIDQ1274917
Marc Demange, Vangelis Th. Paschos, Pascal Grisoni
Publication date: 12 January 1999
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0304-3975(97)00099-6
Related Items (25)
Differential approximation algorithm of FSMVRP ⋮ Differential approximation results for the traveling salesman and related problems ⋮ Fast Heuristics and Approximation Algorithms ⋮ The Bipartite QUBO ⋮ Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : formalisme unifié et classes d'approximation ⋮ An Improved Approximation Bound for Spanning Star Forest and Color Saving ⋮ Approximation and online algorithms for multidimensional bin packing: a survey ⋮ Approximation preserving reductions for set covering, vertex covering and independent set hierarchies under differential approximationa ⋮ Notes on inverse bin-packing problems ⋮ A survey on the structure of approximation classes ⋮ Bridging gap between standard and differential polynomial approximation: The case of bin-packing ⋮ A better differential approximation ratio for symmetric TSP ⋮ Average value of solutions for the bipartite Boolean quadratic programs and rounding algorithms ⋮ COMPLETENESS IN DIFFERENTIAL APPROXIMATION CLASSES ⋮ Reductions, completeness and the hardness of approximability ⋮ On the differential approximation of MIN SET COVER ⋮ Approximation algorithms for the maximum Hamiltonian path problem with specified endpoint(s) ⋮ New differential approximation algorithm for \(k\)-customer vehicle routing problem ⋮ Probabilistic graph-coloring in bipartite and split graphs ⋮ Efficient approximation of Min Set Cover by moderately exponential algorithms ⋮ Differential approximation of NP-hard problems with equal size feasible solutions ⋮ Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances ⋮ Towards a theory of practice in metaheuristics design: A machine learning perspective ⋮ The maximum \(f\)-depth spanning tree problem ⋮ Differential approximation results for the traveling salesman problem with distances 1 and 2
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximation algorithms for indefinite quadratic programming
- Structure preserving reductions among convex optimization problems
- Bin packing can be solved within 1+epsilon in linear time
- A still better performance guarantee for approximate graph coloring
- Approximation algorithms for combinatorial problems
- Three short proofs in graph theory
- On the ratio of optimal integral and fractional covers
- Approximation results for the minimum graph coloring problem
- 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
- On Approximate Solutions for Combinatorial Optimization Problems
- A Greedy Heuristic for the Set-Covering Problem
- Covering edges by cliques with regard to keyword conflicts and intersection graphs
- New approximation algorithms for graph coloring
- On the hardness of approximating minimization problems
This page was built for publication: Differential approximation algorithms for some combinatorial optimization problems
