On (1,)-restricted assignment makespan minimization

DOI10.1137/1.9781611973730.73zbMATH Open1372.68044arXiv1410.7506OpenAlexW4214560154MaRDI QIDQ5363001FDOQ5363001

Authors: Deeparnab Chakrabarty, Sanjeev Khanna, 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)

Abstract: Makespan minimization on unrelated machines is a classic problem in approximation algorithms. No polynomial time $(2-delta)$-approximation algorithm is known for the problem for constant $delta>0$. This is true even for certain special cases, most notably the restricted assignment problem where each job has the same load on any machine but can be assigned to one from a specified subset. Recently in a breakthrough result, Svensson [Svensson, 2011] proved that the integrality gap of a certain configuration LP relaxation is upper bounded by $1.95$ for the restricted assignment problem; however, the rounding algorithm is not known to run in polynomial time. In this paper we consider the $(1,varepsilon)$-restricted assignment problem where each job is either heavy ($p_j=1$) or light ($p_j=varepsilon$), for some parameter $varepsilon>0$. Our main result is a $(2-delta)$-approximate polynomial time algorithm for the $(1,epsilon)$-restricted assignment problem for a fixed constant $delta>0$. Even for this special case, the best polynomial-time approximation factor known so far is 2. We obtain this result by rounding the configuration LP relaxation for this problem. A simple reduction from vertex cover shows that this special case remains NP-hard to approximate to within a factor better than 7/6.

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

Recommendations

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

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)

Cited In (22)

• On some special cases of the restricted assignment problem
• Simpler and Better Algorithms for Minimum-Norm Load Balancing
• A quasi-polynomial approximation for the restricted assignment problem
• A 3/2-approximation algorithm for the graph balancing problem with two weights
• Makespan minimization on unrelated parallel machines with simple job-intersection structure and bounded job assignments
• Restricted assignment scheduling with resource constraints
• Estimating the makespan of the two-valued restricted assignment problem
• Structured instances of restricted assignment with two processing times
• On \((1, \epsilon )\)-restricted max-min fair allocation problem
• On the configuration-LP of the restricted assignment problem
• Computing fair and efficient allocations with few utility values
• Makespan minimization on unrelated parallel machines with a few bags
• Scheduling to minimize total weighted completion time via time-indexed linear programming relaxations
• A PTAS for scheduling unrelated machines of few different types
• The 2-valued case of makespan minimization with assignment constraints
• Approximation algorithms for the graph balancing problem with two speeds and two job lengths
• Better trees for Santa Claus
• Estimating the makespan of the two-valued restricted assignment problem
• Computing fair and efficient allocations with few utility values
• A quasi-polynomial approximation for the restricted assignment problem
• On minimizing the makespan when some jobs cannot be assigned on the same machine
• Lazy local search meets machine scheduling

This page was built for publication: On \((1,\varepsilon)\)-restricted assignment makespan minimization

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