A Primal-Dual Approximation Algorithm for Min-Sum Single-Machine Scheduling Problems
From MaRDI portal
Publication:5346558
DOI10.1137/16M1086819zbMath1365.90226OpenAlexW2611857909MaRDI QIDQ5346558
Julián Mestre, David B. Shmoys, Maurice Cheung, José Verschae
Publication date: 24 May 2017
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/16m1086819
Linear programming (90C05) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27)
Related Items (13)
Dual Techniques for Scheduling on a Machine with Varying Speed ⋮ An Optimal Control Framework for Online Job Scheduling with General Cost Functions ⋮ A Water-Filling Primal-Dual Algorithm for Approximating NonLinear Covering Problems ⋮ Approximation algorithm with constant ratio for stochastic prize-collecting Steiner tree problem ⋮ An unbounded sum-of-squares hierarchy integrality gap for a polynomially solvable problem ⋮ Fixed-parameter algorithms for unsplittable flow cover ⋮ Robust Appointment Scheduling with Heterogeneous Costs ⋮ Optimal algorithms for scheduling under time-of-use tariffs ⋮ How unsplittable-flow-covering helps scheduling with job-dependent cost functions ⋮ Unnamed Item ⋮ Risk-averse single machine scheduling: complexity and approximation ⋮ A polynomial-time approximation scheme for the airplane refueling problem ⋮ A Primal-Dual Approximation Algorithm for Min-Sum Single-Machine Scheduling Problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the Performance of Smith’s Rule in Single-Machine Scheduling with Nonlinear Cost
- Universal Sequencing on an Unreliable Machine
- A Primal-Dual Approximation Algorithm for Min-Sum Single-Machine Scheduling Problems
- Primal-Dual Schema for Capacitated Covering Problems
- Scheduling with Outliers
- Approximability of Sparse Integer Programs
- Valid Linear Inequalities for Fixed Charge Problems
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
- How Unsplittable-Flow-Covering Helps Scheduling with Job-Dependent Cost Functions
- Dual Techniques for Scheduling on a Machine with Varying Speed
- A Primal-Dual Approximation Algorithm for Min-Sum Single-Machine Scheduling Problems
- A Primal-Dual Randomized Algorithm for Weighted Paging
- On the Equivalence between the Primal-Dual Schema and the Local Ratio Technique
- A unified approach to approximating resource allocation and scheduling
This page was built for publication: A Primal-Dual Approximation Algorithm for Min-Sum Single-Machine Scheduling Problems