Journal Article
@Article
Artikel in Fachzeitschrift


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(s)

Author(s):

van Stee, Rob

dblp



BibTeX cite key*:

Stee12

Title

Title*:

An improved algorithm for online rectangle filling

Journal

Journal Title*:

Theoretical Computer Science

Journal's URL:


Download URL
for the article:


Language:

English

Publisher

Publisher's
Name:

Elsevier

Publisher's URL:

http://www.elsevier.com/

Publisher's
Address:

Amsterdam

ISSN:

0304-3975

Vol, No, pp, Date

Volume*:

423

Number:


Publishing Date:

March 2012

Pages*:

59-74

Number of
VG Pages:

16

Page Start:

59

Page End:

74

Sequence Number:


DOI:

10.1016/j.tcs.2011.12.067

Note, Abstract, ©

Note:


(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, and give a better randomized lower bound.
Our results significantly narrow the gap between the best known
upper and lower bound.

URL for the Abstract:


Categories,
Keywords:


HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


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:

@ARTICLE{Stee12,
AUTHOR = {van Stee, Rob},
TITLE = {An improved algorithm for online rectangle filling},
JOURNAL = {Theoretical Computer Science},
PUBLISHER = {Elsevier},
YEAR = {2012},
VOLUME = {423},
PAGES = {59--74},
ADDRESS = {Amsterdam},
MONTH = {March},
ISBN = {0304-3975},
DOI = {10.1016/j.tcs.2011.12.067},
}


Entry last modified by Anja Becker, 02/08/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:49:33 AM
Revisions
2.
1.
0.

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

Edit Dates
08.02.2013 09:59:09
11/14/2012 03:01:43 PM
11/14/2012 11:49:33 AM