Differential approximation of NP-hard problems with equal size feasible solutions
DOI10.1051/RO:2003008zbMATH Open1037.90059OpenAlexW2132239589MaRDI QIDQ4457890FDOQ4457890
Authors: Jérôme Monnot 
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_279_0
Recommendations
- scientific article; zbMATH DE number 2011863
- Differential approximation results for the traveling salesman and related problems
- Differential approximation results for the traveling salesman problem with distances 1 and 2
- scientific article; zbMATH DE number 1839451
- Differential approximation for optimal satisfiability and related problems
Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Analysis of algorithms (68W40) Approximation algorithms (68W25) Abstract computational complexity for mathematical programming problems (90C60)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Approximation algorithms for NP-hard problems.
- A fundamental problem in vehicle routing
- Approximating the weight of shallow Steiner trees
- On the completeness of a generalized matching problem
- Structure preserving reductions among convex optimization problems
- Differential approximation algorithms for some combinatorial optimization problems
- On an approximation measure founded on the links between optimization and polynomial approximation theory
- \(z\)-approximations
- Title not available (Why is that?)
- P-Complete Approximation Problems
- Approximation algorithms for indefinite quadratic programming
- An approximation algorithm for maximum packing of 3-edge paths
- An Analysis of Approximations for Finding a Maximum Weight Hamiltonian Circuit
- Bridging gap between standard and differential polynomial approximation: The case of bin-packing
- Finding k points with minimum diameter and related problems
- Approximation Algorithms for Some Postman Problems
- Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Arc Routing Problems, Part II: The Rural Postman Problem
- Approximate solution of NP optimization problems
- Completeness in approximation classes
- Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
- Analysis of Christofides' heuristic: some paths are more difficult than cycles
- Multicommodity flow models for spanning trees with hop constraints
- Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem
- Title not available (Why is that?)
- Using Variable Redefinition for Computing Lower Bounds for Minimum Spanning and Steiner Trees with Hop Constraints
- Spanning Trees—Short or Small
- Title not available (Why is that?)
- The maximum \(f\)-depth spanning tree problem
- Measuring the Quality of Approximate Solutions to Zero-One Programming Problems
- Title not available (Why is that?)
- Designing reliable tree networks with two cable technologies
- Differential approximation results for the Steiner tree problem
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (2)
This page was built for publication: Differential approximation of NP-hard problems with equal size feasible solutions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4457890)
