A (1+epsilon)-approximation for makespan scheduling with precedence constraints using LP hierarchies

DOI10.1145/2897518.2897532zbMath1373.68454arXiv1509.07808OpenAlexW2412957665MaRDI QIDQ5361827

Elaine Levey, Thomas Rothvoß

Publication date: 29 September 2017

Published in: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

schedulingapproximation algorithmshierarchieslinear programming relaxations

Mathematics Subject Classification ID

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

Related Items (8)

$O(\log^2{k}/\log\log{k})$-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial Time Algorithm ⋮ Speeding-up parallel computation of large smooth-degree isogeny using precedence-constrained scheduling ⋮ Breaking symmetries to rescue sum of squares in the case of makespan scheduling ⋮ Scheduling to Minimize Total Weighted Completion Time via Time-Indexed Linear Programming Relaxations ⋮ Quasi-PTAS for scheduling with precedences using LP hierarchies ⋮ Server cloud scheduling ⋮ An improved approximation algorithm for scheduling under arborescence precedence constraints ⋮ Server cloud scheduling

This page was built for publication: A (1+epsilon)-approximation for makespan scheduling with precedence constraints using LP hierarchies