Approximating vector scheduling: almost matching upper and lower bounds

DOI10.1007/s00453-016-0116-0zbMath1355.68292OpenAlexW2282655154WikidataQ59438516 ScholiaQ59438516MaRDI QIDQ727975

Tjark Vredeveld, Tim Oosterwijk, Ruben van der Zwaan, Nikhil Bansal

Publication date: 21 December 2016

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-016-0116-0

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (4)

Vector scheduling with rejection on two machines ⋮ Approximation and online algorithms for multidimensional bin packing: a survey ⋮ Vector scheduling with rejection on a single machine ⋮ Streaming algorithms for bin packing and vector scheduling

Cites Work

• Unnamed Item
• An application of simultaneous diophantine approximation in combinatorial optimization
• Approximation schemes for scheduling on parallel machines
• The hardness of approximation: Gap location
• Which problems have strongly exponential complexity?
• Carathéodory bounds for integer cones
• Vector assignment schemes for asymmetric settings
• Online Multidimensional Load Balancing
• Integer Programming with a Fixed Number of Variables
• Minkowski's Convex Body Theorem and Integer Programming
• A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
• Vector assignment problems: a general framework
• On Multidimensional Packing Problems
• An EPTAS for Scheduling Jobs on Uniform Processors: Using an MILP Relaxation with a Constant Number of Integral Variables
• Approximating Vector Scheduling: Almost Matching Upper and Lower Bounds

This page was built for publication: Approximating vector scheduling: almost matching upper and lower bounds