Santa Claus Schedules Jobs on Unrelated Machines

DOI10.1137/110851201zbMath1257.68083arXiv1011.1168OpenAlexW2135932424MaRDI QIDQ4907585

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)

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

zbMATH Keywords

linear programmingschedulingpolynomial time algorithmapproximation algorithmsunrelated machinesrestricted assignment problemSanta Claus problem

Mathematics Subject Classification ID

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

Related Items

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