On the Approximability of Single-Machine Scheduling with Precedence Constraints
Ambuehl, Christoph; Mastrolilli, Monaldo; Mutsanas, Nikolaus; Svensson, Ola
2011

Abstract

We consider the single-machine scheduling problem to minimize the weighted sum of completion times under precedence constraints. In a series of recent papers, it was established that this scheduling problem is a special case of minimum weighted vertex cover.

Details

Title On the Approximability of Single-Machine Scheduling with Precedence Constraints
Author(s) Ambuehl, Christoph ; Mastrolilli, Monaldo ; Mutsanas, Nikolaus ; Svensson, Ola
Published in Mathematics Of Operations Research
Volume 36
Pages 653-669
Date 2011
Keywords
DOI https://doi.org/10.1287/moor.1110.0512
Other identifier(s) View record in Web of Science
Laboratories THL2
Record Appears in Scientific production and competences > I&C - School of Computer and Communication Sciences > IINFCOM > THL2 - Theory of Computation Laboratory 2
Peer-reviewed publications
Work produced at EPFL
Journal Articles
Published
Record creation date 2011-12-16

Actions