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

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

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

• 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?)
• 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
• 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)

• The TV advertisements scheduling problem
• scientific article; zbMATH DE number 7561579 (Why is no real title available?)
• The local-global conjecture for scheduling with non-linear cost
• Dual techniques for scheduling on a machine with varying speed
• On scheduling a single machine to minimize a piecewise linear objective function: A compact MIP formulation
• An unbounded sum-of-squares hierarchy integrality gap for a polynomially solvable problem
• A Lasserre lower bound for the min-sum single machine scheduling problem
• Single machine scheduling with job-dependent convex cost and arbitrary precedence constraints
• A primal-dual approximation algorithm for Min-sum single-machine scheduling problems
• On the performance of Smith's rule in single-machine scheduling with nonlinear cost
• Optimal algorithms for scheduling under time-of-use tariffs

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)