Quasi-PTAS for scheduling with precedences using LP hierarchies

DOI10.4230/LIPIcs.ICALP.2018.59zbMath1499.68404arXiv1708.04369OpenAlexW2963881599MaRDI QIDQ5002735

Shashwat Garg

Publication date: 28 July 2021

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

zbMATH Keywords

schedulingapproximation algorithmshierarchiesrounding techniques

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Approximation algorithms (68W25)

Related Items (6)

A 2-approximation for the bounded treewidth sparsest cut problem in \textsf{FPT} Time ⋮ Breaking symmetries to rescue sum of squares in the case of makespan scheduling ⋮ A \(7 / 3\)-approximation algorithm for feedback vertex set in tournaments via Sherali-Adams ⋮ Server cloud scheduling ⋮ An improved approximation algorithm for scheduling under arborescence precedence constraints ⋮ Server cloud scheduling

Cites Work

• Unnamed Item
• Precedence constrained scheduling in \((2-\frac{7}{3p+1})\) optimal
• Polynomial time approximation algorithms for machine scheduling: Ten open problems
• Convex Relaxations and Integrality Gaps
• Conditional hardness of precedence constrained scheduling on identical machines
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• Complexity of Scheduling under Precedence Constraints
• Worst Case Analysis of Two Scheduling Algorithms
• Optimal Long Code Test with One Free Bit
• A (1+epsilon)-approximation for makespan scheduling with precedence constraints using LP hierarchies
• Bounds for Certain Multiprocessing Anomalies
• A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming

This page was built for publication: Quasi-PTAS for scheduling with precedences using LP hierarchies