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.90069OpenAlexW2001258377MaRDI QIDQ1351453
Marc Demange, Vangelis Th. Paschos
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
Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Approximation by polynomials (41A10)
Related Items (38)
Differential approximation algorithm of FSMVRP ⋮ Differential approximation results for the traveling salesman and related problems ⋮ On a resource-constrained scheduling problem with application to distributed systems reconfiguration ⋮ Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications ⋮ 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 preserving reductions for set covering, vertex covering and independent set hierarchies under differential approximationa ⋮ A 3/4 differential approximation algorithm for traveling salesman problem ⋮ Moderately Exponential Approximation: Bridging the Gap Between Exact Computation and Polynomial Approximation ⋮ Dual parameterization and parameterized approximability of subset graph problems ⋮ 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 ⋮ Local approximations for maximum partial subgraph problem. ⋮ A better differential approximation ratio for symmetric TSP ⋮ Differential approximation results for the Steiner tree problem ⋮ Approximation results for the weighted \(P_4\) partition problem ⋮ A branch-and-cut algorithm for a resource-constrained scheduling problem ⋮ A tutorial on the use of graph coloring for some problems in robotics ⋮ COMPLETENESS IN DIFFERENTIAL APPROXIMATION CLASSES ⋮ The robust binomial approach to chance-constrained optimization problems with application to stochastic partitioning of large process networks ⋮ Relationship between superstring and compression measures: new insights on the greedy conjecture ⋮ The generalized vertex cover problem and some variations ⋮ Approximation algorithms for some vehicle routing problems ⋮ 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 ⋮ Differential approximation schemes for half-product related functions and their scheduling applications ⋮ Approximation of the double traveling salesman problem with multiple stacks ⋮ Approximate solution of a resource-constrained scheduling problem ⋮ Efficient approximation of Min Set Cover by moderately exponential algorithms ⋮ Differential approximation of NP-hard problems with equal size feasible solutions ⋮ Differential approximation algorithms for some combinatorial optimization problems ⋮ A new lower bound on approximability of the ground state problem for tridimensional Ising spin glasses ⋮ The maximum \(f\)-depth spanning tree problem ⋮ Differential approximation results for the traveling salesman problem with distances 1 and 2 ⋮ Differential approximation for optimal satisfiability and related problems
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
This page was built for publication: On an approximation measure founded on the links between optimization and polynomial approximation theory
