-optimization schemes and L-bit precision: alternative perspectives for solving combinatorial optimization problems

DOI10.1016/J.DISOPT.2007.08.004MaRDI QIDQ951128zbMATH OpenOpenAlexWikidataFDO

Authors James B. Orlin, Andreas S. Schulz, Sudipta Sengupta

Publication date 29 October 2008

Published in Discrete Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disopt.2007.08.004

zbMATH Keywords

computational complexitycombinatorial optimizationapproximation schemesinverse optimization

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• \({\varepsilon}\)-optimization schemes and \(L\)-bit precision: alternative perspectives in combinatorial optimization (extended abstract)
• Approximate Local Search in Combinatorial Optimization
• Approximate local search in combinatorial optimization
• Efficient Algorithms for Fixed-Precision Instances of Bin Packing and Euclidean TSP
• Publication:3680277

Cites work

• scientific article; zbMATH DE number 3126094 (Why is no real title available?)
• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• Algorithms and Data Structures
• Approximation algorithms for NP-hard problems.
• 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
• Bounds on Multiprocessing Timing Anomalies
• Complexity Results for Multiprocessor Scheduling under Resource Constraints
• Discrete-variable extremum problems
• Exact and Approximate Algorithms for Scheduling Nonidentical Processors
• Integer Programming with a Fixed Number of Variables
• Inverse Optimization
• Network flows. Theory, algorithms, and applications.
• Techniques for scheduling with rejection
• When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?

Cited in

(2)

• Efficient Algorithms for Fixed-Precision Instances of Bin Packing and Euclidean TSP
• \({\varepsilon}\)-optimization schemes and \(L\)-bit precision: alternative perspectives in combinatorial optimization (extended abstract)

This page was built for publication: \(\varepsilon \)-optimization schemes and \(L\)-bit precision: alternative perspectives for solving combinatorial optimization problems

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