On (1,)-restricted assignment makespan minimization

DOI10.1137/1.9781611973730.73MaRDI QIDQ5363001zbMATHOpenAlexFDO

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)

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)

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.

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
• Lazy local search meets machine scheduling

Cited in

(22)

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

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)