On (1,∊)-Restricted Assignment Makespan Minimization

DOI10.1137/1.9781611973730.73zbMath1372.68044arXiv1410.7506OpenAlexW4214560154MaRDI QIDQ5363001

Sanjeev Khanna, Deeparnab Chakrabarty, Shi Li

Publication date: 5 October 2017

Published in: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

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)

Related Items (16)

Makespan minimization on unrelated parallel machines with a few bags ⋮ Computing fair and efficient allocations with few utility values ⋮ Approximation algorithms for the graph balancing problem with two speeds and two job lengths ⋮ Scheduling to Minimize Total Weighted Completion Time via Time-Indexed Linear Programming Relaxations ⋮ Structured Instances of Restricted Assignment with Two Processing Times ⋮ Restricted assignment scheduling with resource constraints ⋮ A Quasi-Polynomial Approximation for the Restricted Assignment Problem ⋮ A 3/2-approximation algorithm for the graph balancing problem with two weights ⋮ Estimating the makespan of the two-valued restricted assignment problem ⋮ On \((1, \epsilon )\)-restricted max-min fair allocation problem ⋮ Computing fair and efficient allocations with few utility values ⋮ A PTAS for Scheduling Unrelated Machines of Few Different Types ⋮ Simpler and Better Algorithms for Minimum-Norm Load Balancing ⋮ Makespan minimization on unrelated parallel machines with simple job-intersection structure and bounded job assignments ⋮ Lazy Local Search Meets Machine Scheduling ⋮ On minimizing the makespan when some jobs cannot be assigned on the same machine

This page was built for publication: On (1,∊)-Restricted Assignment Makespan Minimization