A primal-dual approximation algorithm for min-sum single-machine scheduling problems

DOI10.1007/978-3-642-22935-0_12MaRDI QIDQ3088089zbMATH OpenOpenAlexFDO

Authors 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

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

Abstract: We consider the following single-machine scheduling problem, which is often denoted $1||sum{f}_j$: we are given $n$ jobs to be scheduled on a single machine, where each job $j$ has an integral processing time $p_j$, and there is a nondecreasing, nonnegative cost function $f_j(C_j)$ that specifies the cost of finishing $j$ at time $C_j$; the objective is to minimize $su{m}_{j=1}^n{f}_j(C_j)$. Bansal & Pruhs recently gave the first constant approximation algorithm with a performance guarantee of 16. We improve on this result by giving a primal-dual pseudo-polynomial-time algorithm based on the recently introduced knapsack-cover inequalities. The algorithm finds a schedule of cost at most four times the constructed dual solution. Although we show that this bound is tight for our algorithm, we leave open the question of whether the integrality gap of the LP is less than 4. Finally, we show how the technique can be adapted to yield, for any $epsilon>0$, a $(4+epsilon)$-approximation algorithm for this problem.

Recommendations

• A primal-dual approximation algorithm for Min-sum single-machine scheduling problems
• Optimal algorithms and a PTAS for cost-aware scheduling
• A 1. 47-approximation for a preemptive single-machine scheduling problem
• Single-Machine Scheduling to Minimize a Function of Two or Three Maximum Cost Criteria
• On the performance of Smith's rule in single-machine scheduling with nonlinear cost

Cites work

• A constant factor approximation algorithm for generalized MIN-sum set cover
• A primal-dual randomized algorithm for weighted paging
• A unified approach to approximating resource allocation and scheduling
• Approximability of Sparse Integer Programs
• scientific article; zbMATH DE number 5485535 (Why is no real title available?)
• scientific article; zbMATH DE number 3691044 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1445293 (Why is no real title available?)
• Optimal Sequencing of a Single Machine Subject to Precedence Constraints
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Primal-Dual Schema for Capacitated Covering Problems
• Scheduling with Outliers
• Universal sequencing on a single machine
• Valid Linear Inequalities for Fixed Charge Problems

Cited in

(11)

• An unbounded sum-of-squares hierarchy integrality gap for a polynomially solvable problem
• The TV advertisements scheduling problem
• Optimal algorithms for scheduling under time-of-use tariffs
• The local-global conjecture for scheduling with non-linear cost
• Single machine scheduling with job-dependent convex cost and arbitrary precedence constraints
• Dual techniques for scheduling on a machine with varying speed
• A Lasserre lower bound for the min-sum single machine scheduling problem
• On the performance of Smith's rule in single-machine scheduling with nonlinear cost
• Scheduling to approximate minimization objectives on identical machines
• On scheduling a single machine to minimize a piecewise linear objective function: A compact MIP formulation
• A primal-dual approximation algorithm for Min-sum single-machine scheduling problems

This page was built for publication: A primal-dual approximation algorithm for min-sum single-machine scheduling problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3088089)