\(\varepsilon \)-optimization schemes and \(L\)-bit precision: alternative perspectives for solving combinatorial optimization problems

DOI10.1016/J.DISOPT.2007.08.004zbMath1158.68014OpenAlexW2121972349WikidataQ59592399 ScholiaQ59592399MaRDI QIDQ951128

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

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) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Bin packing can be solved within 1+epsilon in linear time
• Integer Programming with a Fixed Number of Variables
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Inverse Optimization
• Exact and Approximate Algorithms for Scheduling Nonidentical Processors
• Complexity Results for Multiprocessor Scheduling under Resource Constraints
• When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?
• Techniques for scheduling with rejection
• Discrete-Variable Extremum Problems
• Bounds on Multiprocessing Timing Anomalies
• Algorithms and Data Structures

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