Santa Claus schedules jobs on unrelated machines

DOI10.1137/110851201zbMATH Open1257.68083arXiv1011.1168OpenAlexW2135932424MaRDI QIDQ4907585FDOQ4907585

Authors: Ola Svensson 

Publication date: 4 February 2013

Published in: SIAM Journal on Computing, Proceedings of the forty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

Abstract: One of the classic results in scheduling theory is the 2-approximation algorithm by Lenstra, Shmoys, and Tardos for the problem of scheduling jobs to minimize makespan on unrelated machines, i.e., job j requires time p_{ij} if processed on machine i. More than two decades after its introduction it is still the algorithm of choice even in the restricted model where processing times are of the form p_{ij} in {p_j, infty}. This problem, also known as the restricted assignment problem, is NP-hard to approximate within a factor less than 1.5 which is also the best known lower bound for the general version. Our main result is a polynomial time algorithm that estimates the optimal makespan of the restricted assignment problem within a factor 33/17 + epsilon approx 1.9412 + epsilon, where epsilon > 0 is an arbitrarily small constant. The result is obtained by upper bounding the integrality gap of a certain strong linear program, known as configuration LP, that was previously successfully used for the related Santa Claus problem. Similar to the strongest analysis for that problem our proof is based on a local search algorithm that will eventually find a schedule of the mentioned approximation guarantee, but is not known to converge in polynomial time.

Full work available at URL: https://arxiv.org/abs/1011.1168

Recommendations

• Santa Claus schedules jobs on unrelated machines
• On the configuration-LP of the restricted assignment problem
• A quasi-polynomial approximation for the restricted assignment problem
• Approximation algorithms for scheduling unrelated parallel machines
• Lazy local search meets machine scheduling

zbMATH Keywords

linear programmingapproximation algorithmsschedulingpolynomial time algorithmunrelated machinesrestricted assignment problemSanta Claus problem

Mathematics Subject Classification ID

Linear programming (90C05) Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25)

Cited In (36)

• On some special cases of the restricted assignment problem
• Simpler and Better Algorithms for Minimum-Norm Load Balancing
• Scheduling to Minimize Total Weighted Completion Time via Time-Indexed Linear Programming Relaxations
• A 3/2-approximation algorithm for the graph balancing problem with two weights
• Energy-efficient scheduling and routing via randomized rounding
• Restricted assignment scheduling with resource constraints
• Estimating the makespan of the two-valued restricted assignment problem
• Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines
• Santa Claus schedules jobs on unrelated machines
• On \((1, \epsilon )\)-restricted max-min fair allocation problem
• A PTAS for Scheduling Unrelated Machines of Few Different Types
• On the extension complexity of scheduling polytopes
• Integrality gaps for strengthened linear relaxations of capacitated facility location
• Integrality gap analysis for bin packing games
• A Quasi-Polynomial Approximation for the Restricted Assignment Problem
• Title not available (Why is that?)
• Approximate algorithms for unrelated machine scheduling to minimize makespan
• Structured Instances of Restricted Assignment with Two Processing Times
• Graph balancing: a special case of scheduling unrelated parallel machines
• Lazy Local Search Meets Machine Scheduling
• On the configuration LP for maximum budgeted allocation
• Strong LP formulations for scheduling splittable jobs on unrelated machines
• Greedy is optimal for online restricted assignment and smart grid scheduling for unit size jobs
• Structural parameters for scheduling with assignment restrictions
• Breaking symmetries to rescue sum of squares in the case of makespan scheduling
• Scheduling and fixed-parameter tractability
• A note on the integrality gap of the configuration LP for restricted Santa Claus
• On the configuration-LP for scheduling on unrelated machines
• Approximation algorithms for the graph balancing problem with two speeds and two job lengths
• Time-sharing scheduling with tolerance capacities
• Better trees for Santa Claus
• Unrelated parallel machine scheduling -- perspectives and progress
• Resource time-sharing for IoT applications with deadlines
• Title not available (Why is that?)
• On minimizing the makespan when some jobs cannot be assigned on the same machine
• Compact LP Relaxations for Allocation Problems

This page was built for publication: Santa Claus schedules jobs on unrelated machines

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