Efficient Algorithms for Fixed-Precision Instances of Bin Packing and Euclidean TSP

DOI10.1007/978-3-540-85363-3_9zbMath1159.68667OpenAlexW1865188731MaRDI QIDQ3541790

No author found.

Publication date: 27 November 2008

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-85363-3_9

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Cites Work

• An improved fixed-parameter algorithm for vertex cover
• Bin packing can be solved within 1+epsilon in linear time
• The Euclidean traveling salesman problem is NP-complete
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• ε -optimization schemes and L-bit precision (extended abstract)
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Inverse Optimization
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Reducibility among Combinatorial Problems
• Unnamed Item

This page was built for publication: Efficient Algorithms for Fixed-Precision Instances of Bin Packing and Euclidean TSP