Combinatorial algorithms for minimizing the weighted sum of completion times on a single machine

James M. Davis; Rajiv Gandhi; Vijay H. Kothari

doi:10.1016/j.orl.2012.12.001

Combinatorial algorithms for minimizing the weighted sum of completion times on a single machine

James M. Davis
, Rajiv Gandhi
, Vijay H. Kothari

The Rutgers Center for Computational and Integrative Biology (CCIB)

Research output: Contribution to journal › Article › peer-review

7 Scopus citations

Abstract

We study the problem of minimizing the weighted sum of completion times of jobs with release dates on a single machine with the aim of shedding new light on "the simplest (linear program) relaxation" (Queyranne and Schulz, 1994 [17]). Specifically, we analyze a 3-competitive online algorithm (Megow and Schulz, 2004 [16]), using dual fitting. In the offline setting, we develop a primal-dual algorithm with approximation guarantee 1+2. The latter implies that the cost of the optimal schedule is within a factor of 1+2 of the cost of the optimal LP solution.

Original language	English (US)
Pages (from-to)	121-125
Number of pages	5
Journal	Operations Research Letters
Volume	41
Issue number	2
DOIs	https://doi.org/10.1016/j.orl.2012.12.001
State	Published - Mar 2013

All Science Journal Classification (ASJC) codes

Software
Management Science and Operations Research
Industrial and Manufacturing Engineering
Applied Mathematics

Keywords

Algorithms
Approximation
Dual fitting
Online
Primal-dual
Scheduling

Access to Document

10.1016/j.orl.2012.12.001

Cite this

@article{20e652f28b6c438b9a86df7ebef6373c,

title = "Combinatorial algorithms for minimizing the weighted sum of completion times on a single machine",

abstract = "We study the problem of minimizing the weighted sum of completion times of jobs with release dates on a single machine with the aim of shedding new light on {"}the simplest (linear program) relaxation{"} (Queyranne and Schulz, 1994 [17]). Specifically, we analyze a 3-competitive online algorithm (Megow and Schulz, 2004 [16]), using dual fitting. In the offline setting, we develop a primal-dual algorithm with approximation guarantee 1+2. The latter implies that the cost of the optimal schedule is within a factor of 1+2 of the cost of the optimal LP solution.",

keywords = "Algorithms, Approximation, Dual fitting, Online, Primal-dual, Scheduling",

author = "Davis, \{James M.\} and Rajiv Gandhi and Kothari, \{Vijay H.\}",

note = "Funding Information: This research was supported by NSF awards 0830569 and 1050968 . Part of this work was done when James Davis was an undergraduate student at Rutgers University-Camden and Vijay Kothari was visiting Rutgers University-Camden as a post-baccalaureate student. We are very grateful to an anonymous referee for a very thorough report and for suggesting various improvements in the write-up of this paper.",

year = "2013",

month = mar,

doi = "10.1016/j.orl.2012.12.001",

language = "English (US)",

volume = "41",

pages = "121--125",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "2",

}

TY - JOUR

T1 - Combinatorial algorithms for minimizing the weighted sum of completion times on a single machine

AU - Davis, James M.

AU - Gandhi, Rajiv

AU - Kothari, Vijay H.

N1 - Funding Information: This research was supported by NSF awards 0830569 and 1050968 . Part of this work was done when James Davis was an undergraduate student at Rutgers University-Camden and Vijay Kothari was visiting Rutgers University-Camden as a post-baccalaureate student. We are very grateful to an anonymous referee for a very thorough report and for suggesting various improvements in the write-up of this paper.

PY - 2013/3

Y1 - 2013/3

N2 - We study the problem of minimizing the weighted sum of completion times of jobs with release dates on a single machine with the aim of shedding new light on "the simplest (linear program) relaxation" (Queyranne and Schulz, 1994 [17]). Specifically, we analyze a 3-competitive online algorithm (Megow and Schulz, 2004 [16]), using dual fitting. In the offline setting, we develop a primal-dual algorithm with approximation guarantee 1+2. The latter implies that the cost of the optimal schedule is within a factor of 1+2 of the cost of the optimal LP solution.

AB - We study the problem of minimizing the weighted sum of completion times of jobs with release dates on a single machine with the aim of shedding new light on "the simplest (linear program) relaxation" (Queyranne and Schulz, 1994 [17]). Specifically, we analyze a 3-competitive online algorithm (Megow and Schulz, 2004 [16]), using dual fitting. In the offline setting, we develop a primal-dual algorithm with approximation guarantee 1+2. The latter implies that the cost of the optimal schedule is within a factor of 1+2 of the cost of the optimal LP solution.

KW - Algorithms

KW - Approximation

KW - Dual fitting

KW - Online

KW - Primal-dual

KW - Scheduling

UR - https://www.scopus.com/pages/publications/84871555834

UR - https://www.scopus.com/pages/publications/84871555834#tab=citedBy

U2 - 10.1016/j.orl.2012.12.001

DO - 10.1016/j.orl.2012.12.001

M3 - Article

AN - SCOPUS:84871555834

SN - 0167-6377

VL - 41

SP - 121

EP - 125

JO - Operations Research Letters

JF - Operations Research Letters

IS - 2

ER -

Combinatorial algorithms for minimizing the weighted sum of completion times on a single machine

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this