Quasi-PTAS for scheduling with precedences using LP hierarchies
From MaRDI portal
Publication:5002735
DOI10.4230/LIPIcs.ICALP.2018.59zbMath1499.68404arXiv1708.04369OpenAlexW2963881599MaRDI QIDQ5002735
Publication date: 28 July 2021
Full work available at URL: https://arxiv.org/abs/1708.04369
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
