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:








Author, Editor(s)

Author(s):

Doerr, Benjamin

dblp



BibTeX cite key*:

RandCol2006

Title

Title*:

Non-independent randomized rounding and coloring

Journal

Journal Title*:

Discrete Applied Mathematics

Journal's URL:


Download URL
for the article:

http://www.sciencedirect.com/science?_ob=MImg&_imagekey=B6TYW-4HG69G9-1-DF&_cdi=5629&_user=43521&_orig=search&_coverDate=03%2F15%2F2006&_sk=998459995&view=c&wchp=dGLbVzb-zSkWA&md5=15aef4648a2832e5b6c8339a29a735e5&ie=/sdarticle.pdf

Language:

English

Publisher

Publisher's
Name:

Elsevier

Publisher's URL:

http://www.elsevier.com/

Publisher's
Address:

Amsterdam, The Netherlands

ISSN:


Vol, No, pp, Date

Volume*:

154

Number:

4

Publishing Date:

2006

Pages*:

650-659

Number of
VG Pages:

22

Page Start:


Page End:


Sequence Number:


DOI:


Note, Abstract, ©

Note:


(LaTeX) Abstract:


We propose an advanced randomized coloring algorithm for the problem of balanced colorings of hypergraphs (discrepancy problem). Instead of independently coloring the vertices with a random color, we try to use structural information about the hypergraph in the design of the random experiment by imposing suitable dependencies. This yields colorings having smaller discrepancy. We also obtain more information about the coloring, or, conversely, we may enforce the random coloring to have special properties. There are some algorithmic advantages as well.

We apply our approach to hypergraphs of d-dimensional boxes and to finite geometries. Among others results, we gain a factor 2d/2 decrease in the discrepancy of the boxes, and reduce the number of random bits needed to generate good colorings for the geometries down to Click to view the MathML source(from n). The latter also speeds up the corresponding derandomization by a factor of Click to view the MathML source.


URL for the Abstract:

http://portal.acm.org/citation.cfm?id=1141038.1141043
http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6TYW-4HG69G9-1&_user=43521&_coverDate=03%2F15%2F2006&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_acct=C000004638&_version=1&_urlVersion=0&_userid=43521&md5=7d33fcead870aa5a8ce2c4e442527729

Categories,
Keywords:

Randomized Rounding

HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:

Intranet

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{RandCol2006,
AUTHOR = {Doerr, Benjamin},
TITLE = {Non-independent randomized rounding and coloring},
JOURNAL = {Discrete Applied Mathematics},
PUBLISHER = {Elsevier},
YEAR = {2006},
NUMBER = {4},
VOLUME = {154},
PAGES = {650--659},
ADDRESS = {Amsterdam, The Netherlands},
}


Entry last modified by Christine Kiesel, 02/05/2007
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)
Mathias Bader
Created
11/22/2006 05:35:12 PM
Revisions
3.
2.
1.
0.
Editor(s)
Christine Kiesel
Christine Kiesel
Mathias Bader
Mathias Bader
Edit Dates
05.02.2007 20:11:39
05.02.2007 20:10:38
10.12.2006 18:58:19
22.11.2006 17:35:12