On the configuration-LP of the restricted assignment problem

DOI10.1137/1.9781611974782.176MaRDI QIDQ4575925zbMATH OpenOpenAlexFDO

Authors Lars Rohwedder, Klaus Jansen

Publication date 16 July 2018

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

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

zbMATH Keywords

estimation algorithmsintegrality gaplinear programminglocal searchscheduling

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Deterministic scheduling theory in operations research (90B35) Discrete location and assignment (90B80) Linear programming (90C05)

Abstract: We consider the classical problem of Scheduling on Unrelated Machines. In this problem a set of jobs is to be distributed among a set of machines and the maximum load (makespan) is to be minimized. The processing time $p_{ij}$ of a job $j$ depends on the machine $i$ it is assigned to. Lenstra, Shmoys and Tardos gave a polynomial time $2$-approximation for this problem. In this paper we focus on a prominent special case, the Restricted Assignment problem, in which $p_{ij}in{p}_j,infty$. The configuration-LP is a linear programming relaxation for the Restricted Assignment problem. It was shown by Svensson that the multiplicative gap between integral and fractional solution, the integrality gap, is at most $2-1/17approx1.9412$. In this paper we significantly simplify his proof and achieve a bound of $2-1/6approx1.8333$. As a direct consequence this provides a polynomial $(2-1/6+epsilon)$-estimation algorithm for the Restricted Assignment problem by approximating the configuration-LP. The best lower bound known for the integrality gap is $1.5$ and no estimation algorithm with a guarantee better than $1.5$ exists unless $mathrmP=mathrmNP$.

Recommendations

• A quasi-polynomial approximation for the restricted assignment problem
• On (1,)-restricted assignment makespan minimization
• On the Configuration-LP for Scheduling on Unrelated Machines
• On the configuration-LP for scheduling on unrelated machines
• Estimating the makespan of the two-valued restricted assignment problem

Cited in

(24)

• Adjacency on the constrained assignment problem
• Estimating the makespan of the two-valued restricted assignment problem
• Makespan minimization on unrelated parallel machines with a few bags
• A note on the integrality gap of the configuration LP for restricted Santa Claus
• A quasi-polynomial approximation for the restricted assignment problem
• Approximation algorithms for the graph balancing problem with two speeds and two job lengths
• On some special cases of the restricted assignment problem
• Structured instances of restricted assignment with two processing times
• scientific article; zbMATH DE number 4081306 (Why is no real title available?)
• On the configuration-LP for scheduling on unrelated machines
• Simpler and Better Algorithms for Minimum-Norm Load Balancing
• Graph balancing with orientation costs
• Capacitated dynamic programming: faster knapsack and graph algorithms
• Local search breaks 1.75 for graph balancing
• Scheduling to minimize total weighted completion time via time-indexed linear programming relaxations
• A quasi-polynomial approximation for the restricted assignment problem
• Lazy local search meets machine scheduling
• Compact LP relaxations for allocation problems
• On (1,)-restricted assignment makespan minimization
• Estimating the makespan of the two-valued restricted assignment problem
• On min-max graph balancing with strict negative correlation constraints
• Improved integrality gap in max-min allocation, or, topology at the north pole
• Additive approximation schemes for load balancing problems
• Strong LP formulations for scheduling splittable jobs on unrelated machines

This page was built for publication: On the configuration-LP of the restricted assignment problem

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