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

DOI10.1007/978-3-540-85363-3_9MaRDI QIDQ3541790zbMATH OpenOpenAlexFDO

Authors

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

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

Recommendations

• Bin packing with fixed number of bins revisited
• Bin packing with fixed number of bins revisited
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• scientific article; zbMATH DE number 1163704
• -optimization schemes and L-bit precision: alternative perspectives for solving combinatorial optimization problems

Cites work

• \({\varepsilon}\)-optimization schemes and \(L\)-bit precision: alternative perspectives in combinatorial optimization (extended abstract)
• An improved fixed-parameter algorithm for vertex cover
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Bin packing can be solved within 1+epsilon in linear time
• Fixed-Parameter Tractability and Completeness I: Basic Results
• scientific article; zbMATH DE number 3689144 (Why is no real title available?)
• Inverse Optimization
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Reducibility among combinatorial problems
• The Euclidean traveling salesman problem is NP-complete

Cited in

(2)

• \({\varepsilon}\)-optimization schemes and \(L\)-bit precision: alternative perspectives in combinatorial optimization (extended abstract)
• -optimization schemes and L-bit precision: alternative perspectives for solving combinatorial optimization problems

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3541790)