Search

Your search keyword '"SITTERS, RENÉ"' showing total 31 results
Start Over Author "SITTERS, RENÉ" Publication Year Range Last 10 years
31 results on '"SITTERS, RENÉ"'

1. A $(2 + \epsilon)$-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective

Author

Sitters, René and Yang, Liya

Subjects
Computer Science - Data Structures and Algorithms, Mathematics - Optimization and Control
Abstract

We give a $(2 + \epsilon)$-approximation algorithm for minimizing total weighted completion time on a single machine under release time and precedence constraints. This settles a recent conjecture made in [18]

Published
2017

2. The triangle scheduling problem

Author

Dürr, Christoph, Hanzálek, Zdeněk, Konrad, Christian, Seddik, Yasmina, Sitters, René, Vásquez, Óscar C., and Woeginger, Gerhard

Subjects
Computer Science - Data Structures and Algorithms
Abstract

This paper introduces a novel scheduling problem, where jobs occupy a triangular shape on the time line. This problem is motivated by scheduling jobs with different criticality levels. A measure is introduced, namely the binary tree ratio. It is shown that the greedy algorithm solves the problem to optimality when the binary tree ratio of the input instance is at most 2. We also show that the problem is unary NP-hard for instances with binary tree ratio strictly larger than 2, and provide a quasi polynomial time approximation scheme (QPTAS). The approximation ratio of Greedy on general instances is shown to be between 1.5 and 1.05.

Published
2016

3. Fixed-Order Scheduling on Parallel Machines

Author

Bosman, Thomas, Frascaria, Dario, Olver, Neil, Sitters, René, Stougie, Leen, Hutchison, David, Editorial Board Member, Kanade, Takeo, Editorial Board Member, Kittler, Josef, Editorial Board Member, Kleinberg, Jon M., Editorial Board Member, Mattern, Friedemann, Editorial Board Member, Mitchell, John C., Editorial Board Member, Naor, Moni, Editorial Board Member, Pandu Rangan, C., Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Terzopoulos, Demetri, Editorial Board Member, Tygar, Doug, Editorial Board Member, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Lodi, Andrea, editor, and Nagarajan, Viswanath, editor

Published
2019
Full Text
View/download PDF

5. The Itinerant List Update Problem

Author

Olver, Neil, Pruhs, Kirk, Schewior, Kevin, Sitters, René, Stougie, Leen, Hutchison, David, Series Editor, Kanade, Takeo, Series Editor, Kittler, Josef, Series Editor, Kleinberg, Jon M., Series Editor, Mattern, Friedemann, Series Editor, Mitchell, John C., Series Editor, Naor, Moni, Series Editor, Pandu Rangan, C., Series Editor, Steffen, Bernhard, Series Editor, Terzopoulos, Demetri, Series Editor, Tygar, Doug, Series Editor, Weikum, Gerhard, Series Editor, Epstein, Leah, editor, and Erlebach, Thomas, editor

Published
2018
Full Text
View/download PDF

7. A priori TSP in the Scenario Model

Author

van Ee, Martijn, van Iersel, Leo, Janssen, Teun, Sitters, René, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Jansen, Klaus, editor, and Mastrolilli, Monaldo, editor

Published
2017
Full Text
View/download PDF

10. On the Complexity of Master Problems

Author

van Ee, Martijn, Sitters, René, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Italiano, Giuseppe F., editor, Pighizzini, Giovanni, editor, and Sannella, Donald T., editor

Published
2015
Full Text
View/download PDF

11. Routing Under Uncertainty: The a priori Traveling Repairman Problem

Author

van Ee, Martijn, Sitters, René, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Bampis, Evripidis, editor, and Svensson, Ola, editor

Published
2015
Full Text
View/download PDF

22. A (2+ϵ)-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective

Author

Sitters, René, Yang, Liya, Econometrics and Operations Research, Amsterdam Business Research Institute, and Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands

Subjects
Scheduling, Total weighted completion time, Precedence constraints, SDG 7 - Affordable and Clean Energy, Approximation algorithm
Abstract

We give a (2+ϵ)-approximation algorithm for minimizing total weighted completion time on a single machine under release time and precedence constraints. This settles a recent conjecture on the approximability of this scheduling problem (Skutella, 2016).

Published
2018

27. The triangle scheduling problem

Author

Dürr, Christoph, primary, Hanzálek, Zdeněk, additional, Konrad, Christian, additional, Seddik, Yasmina, additional, Sitters, René, additional, Vásquez, Óscar C., additional, and Woeginger, Gerhard, additional

Published
2017
Full Text
View/download PDF

31. Minimizing worst-case and average-case makespan over scenarios.

Author

Feuerstein, Esteban, Marchetti-Spaccamela, Alberto, Schalekamp, Frans, Sitters, René, Ster, Suzanne, Stougie, Leen, and Zuylen, Anke

Subjects
PRODUCTION scheduling, APPROXIMATION theory, MATHEMATICAL bounds, COMBINATORIAL optimization, MACHINE theory
Abstract

We consider scheduling problems over scenarios where the goal is to find a single assignment of the jobs to the machines which performs well over all scenarios in an explicitly given set. Each scenario is a subset of jobs that must be executed in that scenario. The two objectives that we consider are minimizing the maximum makespan over all scenarios and minimizing the sum of the makespans of all scenarios. For both versions, we give several approximation algorithms and lower bounds on their approximability. We also consider some (easier) special cases. Combinatorial optimization problems under scenarios in general, and scheduling problems under scenarios in particular, have seen only limited research attention so far. With this paper, we make a step in this interesting research direction. [ABSTRACT FROM AUTHOR]

Published
2017
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results