MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
van Stee, Robdblp
Editor(s):
Jansen, Klaus
Solis-Oba, Roberto		dblp
dblp
Not MPII Editor(s):
Jansen, Klaus
Solis-Oba, Roberto
BibTeX cite key*:
vanStee2010
Title, Booktitle
Title*:
An improved algorithm for online rectangle filling
recfillingJ.pdf (177.25 KB)
Booktitle*:
Approximation and Online Algorithms : 8th International Workshop, WAOA 2010
Event, URLs
Conference URL::
Downloading URL:
http://dx.doi.org/10.1007/978-3-642-18318-8_22
Event Address*:
Liverpool, Great Britain
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
9 September 2010
Event End Date:
10 September 2010
Publisher
Name*:
Springer
URL:
http://www.springer-ny.com/
Address*:
Berlin
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
6534
Number:
Month:
January
Pages:
249-260
Year*:
2011
VG Wort Pages:
12
ISBN/ISSN:
978-3-642-18317-1
Sequence Number:
DOI:
10.1007/978-3-642-18318-8_22
Note, Abstract, ©
(LaTeX) Abstract:
We consider the problem of scheduling resource allocation where a
change in allocation results in a changeover penalty of one time
slot. We assume that we are sending packets over a wireless
channel of uncertain and varying capacity. In each time slot,
a bandwidth of at most the
current capacity can be allocated, but changing the capacity has a cost,
which is modeled as an empty time slot.
Only the current bandwidth and the bandwidth of the immediately
following slot are known. We give an online algorithm
with competitive ratio 1.753 for this problem, improving over the
previous upper bound of 1.848. The main new idea of our algorithm is that
it attempts to avoid cases where a single time slot with a nonzero
allocation is immediately followed by an empty time slot.
Additionally, we improve the lower bound for this problem to 1.6959.
Our results significantly narrow the gap between the best known
upper and lower bound.
Keywords:
online algorithms
Download
Access Level:
Public

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{vanStee2010,
AUTHOR = {van Stee, Rob},
 EDITOR = {Jansen, Klaus and Solis-Oba, Roberto},
 TITLE = {An improved algorithm for online rectangle filling},
 BOOKTITLE = {Approximation and Online Algorithms : 8th International Workshop, WAOA 2010},
 PUBLISHER = {Springer},
 YEAR = {2011},
 VOLUME = {6534},
 PAGES = {249--260},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Liverpool, Great Britain},
 MONTH = {January},
 ISBN = {978-3-642-18317-1},
 DOI = {10.1007/978-3-642-18318-8_22},
}

Entry last modified by Anja Becker, 02/14/2012
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
12/09/2010 15:52:59
Revisions
2.
1.
0.

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

Edit Dates
14.02.2012 11:32:09
02-10-2011 11:23:39
12-09-2010 15:52:59

File Attachment Icon
recfillingJ.pdf