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):

van Stee, Rob

dblp



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

URL of the conference:


URL for downloading the paper:

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
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
12/09/2010 03:52:59 PM
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

Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section

View attachments here:


File Attachment Icon
recfillingJ.pdf