On an approximation measure founded on the links between optimization and polynomial approximation theory
From MaRDI portal
Publication:1351453
DOI10.1016/0304-3975(95)00060-7zbMath0871.90069MaRDI QIDQ1351453
Vangelis Th. Paschos, Marc Demange
Publication date: 27 February 1997
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(95)00060-7
68Q25: Analysis of algorithms and problem complexity
90C27: Combinatorial optimization
41A10: Approximation by polynomials
Related Items
Differential approximation of NP-hard problems with equal size feasible solutions, Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : formalisme unifié et classes d'approximation, Approximation preserving reductions for set covering, vertex covering and independent set hierarchies under differential approximationa, COMPLETENESS IN DIFFERENTIAL APPROXIMATION CLASSES, Approximation algorithms for the maximum Hamiltonian path problem with specified endpoint(s), A better differential approximation ratio for symmetric TSP, Approximation results for the weighted \(P_4\) partition problem, A tutorial on the use of graph coloring for some problems in robotics, New differential approximation algorithm for \(k\)-customer vehicle routing problem, Approximate solution of a resource-constrained scheduling problem, Efficient approximation of Min Set Cover by moderately exponential algorithms, Differential approximation algorithms for some combinatorial optimization problems, A new lower bound on approximability of the ground state problem for tridimensional Ising spin glasses, Local approximations for maximum partial subgraph problem., Differential approximation results for the Steiner tree problem, The maximum \(f\)-depth spanning tree problem, Approximation algorithms for some vehicle routing problems, On the differential approximation of MIN SET COVER, Differential approximation results for the traveling salesman problem with distances 1 and 2, Differential approximation for optimal satisfiability and related problems, Bridging gap between standard and differential polynomial approximation: The case of bin-packing, On a resource-constrained scheduling problem with application to distributed systems reconfiguration, Reductions, completeness and the hardness of approximability, A branch-and-cut algorithm for a resource-constrained scheduling problem, An Improved Approximation Bound for Spanning Star Forest and Color Saving
Cites Work
- Heuristic evaluation techniques for bin packing approximation algorithms
- Structure preserving reductions among convex optimization problems
- Optimization, approximation, and complexity classes
- Improved approximations for maximum independent set via approximation chains
- On Approximate Solutions for Combinatorial Optimization Problems
- Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
- P-Complete Approximation Problems
- Two-Processor Scheduling with Start-Times and Deadlines
- An analysis of approximations for maximizing submodular set functions—I
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
