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:








Author, Editor

Author(s):

Vöcking, Berthold

dblp



Editor(s):





BibTeX cite key*:

Voecking2001c

Title, Booktitle

Title*:

Symmetric vs. Asymmetric Multiple-Choice Algorithms

Booktitle*:

Proceedings of the 2nd International Workshop on Approximation and Randomized Algorithms in Communication Networks (ARACNE)

Event, URLs

URL of the conference:


URL for downloading the paper:


Event Address*:

Aarhus

Language:

English

Event Date*
(no longer used):

August, 27, 2001

Organization:


Event Start Date:

27 August 2001

Event End Date:

27 August 2001

Publisher

Name*:

Carleton Scientific

URL:


Address*:

Waterloo, Ontario, Canada

Type:


Vol, No, Year, pp.

Series:


Volume:


Number:


Month:


Pages:

1-10

Year*:

2001

VG Wort Pages:


ISBN/ISSN:


Sequence Number:


DOI:




Note, Abstract, ©


(LaTeX) Abstract:

Multiple-choice allocation algorithms have been studied intensively
over the last decade. These algorithms have several applications
in the areas of load balancing, routing, resource allocation and
hashing. The underlying idea is simple and can be explained best
in the balls-and-bins model: Instead of assigning balls
(jobs, requests, or keys) simply at random to bins (machines, servers,
or positions in a hash table), choose first a small set of bins at
random, inspect these bins, and place the ball into one of the bins
containing the smallest number of balls among them.

The simple idea of first selecting a small set of alternatives at
random and then making the final choice after careful inspection of
these alternatives leads to great improvements against algorithms
that place their decisions simply at random. We illustrate the power
of this principle in terms of simple balls-and-bins processes.
In particular, we study recently presented algorithms that
treat bins asymmetrically in order to obtain a better load balancing.
We compare the behavior of these asymmetric schemes with symmetric
schemes and prove that the asymmetric schemes achieve a better load
balancing than their symmetric counterparts.



Download
Access Level:

Public

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Audience:

Expert

Appearance:

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



BibTeX Entry:

@INPROCEEDINGS{Voecking2001c,
AUTHOR = {V{\"o}cking, Berthold},
TITLE = {Symmetric vs. Asymmetric Multiple-Choice Algorithms},
BOOKTITLE = {Proceedings of the 2nd International Workshop on Approximation and Randomized Algorithms in Communication Networks (ARACNE)},
PUBLISHER = {Carleton Scientific},
YEAR = {2001},
PAGES = {1--10},
ADDRESS = {Aarhus},
}


Entry last modified by Uwe Brahm, 03/02/2010
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)
Berthold Voecking
Created
03/17/2002 05:52:10 PM
Revision
1.
0.


Editor
Uwe Brahm
Berthold Voecking


Edit Date
02/14/2005 09:44:33 PM
17/03/2002 17:52:10


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