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

DOI10.1007/978-3-642-22935-0_12zbMATH Open1343.68310arXiv1612.03339OpenAlexW1933011002MaRDI QIDQ3088089FDOQ3088089

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)

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.

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

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (11)

• The TV advertisements scheduling problem
• Title not available (Why is that?)
• 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
• A Lasserre lower bound for the min-sum single machine scheduling problem
• 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
• 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)