A Primal-Dual Approximation Algorithm for Min-Sum Single-Machine Scheduling Problems

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

zbMATH Keywords

approximation algorithmprimal-dual schemaknapsack-cover inequalitieMin-sum scheduling

Mathematics Subject Classification ID

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