Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:




Library Locked Library locked




Author, Editor

Author(s):

Epstein, Leah
Jez, Lukasz
Sgall, Jiri
van Stee, Rob

dblp
dblp
dblp
dblp

Not MPG Author(s):

Epstein, Leah
Jez, Lukasz
Sgall, Jiri

Editor(s):

Gupta, Anupam
Jansen, Klaus
Rolim, José
Servedio, Rocco

dblp
dblp
dblp
dblp

Not MPII Editor(s):

Gupta, Anupam
Jansen, Klaus
Rolim, José
Servedio, Rocco

BibTeX cite key*:

EpJeSS12

Title, Booktitle

Title*:

Online Scheduling of Jobs with Fixed Start Times on Related Machines

Booktitle*:

Approximation, Randomization, and Combinatorial Optimization : Algorithms and Techniques ; 15th International Workshop, APPROX 2012 and 16th International Workshop, RANDOM 2012

Event, URLs

URL of the conference:

http://cui.unige.ch/tcs/random-approx/2012/index.php

URL for downloading the paper:


Event Address*:

Boston, USA

Language:

English

Event Date*
(no longer used):


Organization:


Event Start Date:

15 August 2012

Event End Date:

17 August 2012

Publisher

Name*:

Springer

URL:

http://www.springer-ny.com/

Address*:

Berlin

Type:


Vol, No, Year, pp.

Series:

Lecture Notes in Computer Science

Volume:

7408

Number:


Month:

August

Pages:

134-145

Year*:

2012

VG Wort Pages:

12

ISBN/ISSN:

978-3-642-32511-3

Sequence Number:


DOI:

10.1007/978-3-642-32512-0_12



Note, Abstract, ©


(LaTeX) Abstract:

We consider online preemptive throughput scheduling of jobs with fixed
starting times on $m$ uniformly related machines, with the goal of
maximizing the profit of the completed jobs. In this problem, jobs are
released over time. Every job has a size and a weight associated with
it. A newly released job must be either assigned to start running
immediately on a machine or otherwise it is dropped. It is also
possible to drop an already scheduled job, but only completed jobs
contribute their weights to the profit of the algorithm.

In the most general setting, no algorithm has bounded competitive
ratio, and we consider a number of standard variants. We give a full
classification of the variants into cases which admit constant
competitive ratio (weighted and unweighted unit jobs, and C-benevolent
instances, which is a wide class of instances containing
proportional-weight jobs), and cases which admit only a linear
competitive ratio (unweighted jobs and D-benevolent instances). In
particular, we give a lower bound of $m$ on the competitive ratio for
scheduling unit weight jobs with varying sizes, which is tight. For
unit size and weight we show that a natural greedy algorithm is
$4/3$-competitive and optimal on $m=2$ machines, while for a large
$m$, its competitive ratio is between $1.56$ and $2$. Furthermore, no
algorithm is better than $1.5$-competitive.



Download
Access Level:

Internal

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{EpJeSS12,
AUTHOR = {Epstein, Leah and Jez, Lukasz and Sgall, Jiri and van Stee, Rob},
EDITOR = {Gupta, Anupam and Jansen, Klaus and Rolim, Jos{\'e} and Servedio, Rocco},
TITLE = {Online Scheduling of Jobs with Fixed Start Times on Related Machines},
BOOKTITLE = {Approximation, Randomization, and Combinatorial Optimization : Algorithms and Techniques ; 15th International Workshop, APPROX 2012 and 16th International Workshop, RANDOM 2012},
PUBLISHER = {Springer},
YEAR = {2012},
VOLUME = {7408},
PAGES = {134--145},
SERIES = {Lecture Notes in Computer Science},
ADDRESS = {Boston, USA},
MONTH = {August},
ISBN = {978-3-642-32511-3},
DOI = {10.1007/978-3-642-32512-0_12},
}


Entry last modified by Anja Becker, 02/06/2013
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]
Created
11/14/2012 11:58:51 AM
Revisions
2.
1.
0.

Editor(s)
Anja Becker
Rob van Stee
Rob van Stee

Edit Dates
31.01.2013 16:48:11
11/14/2012 03:02:23 PM
11/14/2012 11:58:51 AM