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

DOI10.1007/978-3-642-22935-0_12zbMath1343.68310arXiv1612.03339OpenAlexW1933011002MaRDI QIDQ3088089

Maurice Cheung, David B. Shmoys

Publication date: 17 August 2011

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

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

Mathematics Subject Classification ID

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

Related Items (8)

A Lasserre Lower Bound for the Min-Sum Single Machine Scheduling Problem ⋮ The local-global conjecture for scheduling with non-linear cost ⋮ An unbounded sum-of-squares hierarchy integrality gap for a polynomially solvable problem ⋮ Single machine scheduling with job-dependent convex cost and arbitrary precedence constraints ⋮ The TV advertisements scheduling problem ⋮ Optimal algorithms for scheduling under time-of-use tariffs ⋮ Unnamed Item ⋮ A Primal-Dual Approximation Algorithm for Min-Sum Single-Machine Scheduling Problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Primal-Dual Schema for Capacitated Covering Problems
• Universal Sequencing on a Single Machine
• 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
• A Primal-Dual Randomized Algorithm for Weighted Paging
• Optimal Sequencing of a Single Machine Subject to Precedence Constraints
• 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