Santa Claus Schedules Jobs on Unrelated Machines

DOI10.1137/110851201zbMath1257.68083arXiv1011.1168MaRDI 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 programming; scheduling; polynomial time algorithm; approximation algorithms; unrelated machines; restricted assignment problem; Santa Claus problem

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

90C05: Linear programming

90B35: Deterministic scheduling theory in operations research

68M20: Performance evaluation, queueing, and scheduling in the context of computer systems

68W25: Approximation algorithms