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

Doerr, Benjamin

dblp



Editor(s):

Durand, Bruno
Thomas, Wolfgang

dblp
dblp

Not MPII Editor(s):

Durand, Bruno
Thomas, Wolfgang

BibTeX cite key*:

DoerrStacs2006

Title, Booktitle

Title*:

Generating Randomized Roundings with Cardinality Constraints and Derandomizations

Booktitle*:

STACS 2006, 23rd Annual Symposium on Theoretical Aspects of Computer Science

Event, URLs

URL of the conference:


URL for downloading the paper:

http://www.springerlink.com/content/y480652353726q37/fulltext.pdf

Event Address*:

Marseille, France

Language:

English

Event Date*
(no longer used):


Organization:


Event Start Date:

23 February 2006

Event End Date:

25 February 2006

Publisher

Name*:

Springer

URL:


Address*:

Berlin, Germany

Type:


Vol, No, Year, pp.

Series:

Lecture Notes in Computer Science

Volume:

3884

Number:


Month:


Pages:

571-583

Year*:

2006

VG Wort Pages:


ISBN/ISSN:

3-540-32301-5

Sequence Number:


DOI:




Note, Abstract, ©


(LaTeX) Abstract:

We provide a general method to generate randomized roundings that satisfy cardinality constraints. Our approach is different from the one taken by Srinivasan (FOCS 2001) and Gandhi et al. (FOCS 2002) for one global constraint and the bipartite edge weight rounding problem.
Also for these special cases, our approach is the first that can be derandomized. For the bipartite edge weight rounding problem, in addition, we gain an factor run-time improvement for generating the randomized solution.
We also improve the current best result on the general problem of derandomizing randomized roundings. Here we obtain a simple O(mnlog n) time algorithm that works in the RAM model for arbitrary matrices with entries in . This improves over the O(mn2 log(mn)) time solution of Srivastav and Stangier.

URL for the Abstract:

http://dx.doi.org/10.1007/11672142_47
http://www.springerlink.com/content/y480652353726q37/



Download
Access Level:

Internal

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{DoerrStacs2006,
AUTHOR = {Doerr, Benjamin},
EDITOR = {Durand, Bruno and Thomas, Wolfgang},
TITLE = {Generating Randomized Roundings with Cardinality Constraints and Derandomizations},
BOOKTITLE = {STACS 2006, 23rd Annual Symposium on Theoretical Aspects of Computer Science},
PUBLISHER = {Springer},
YEAR = {2006},
VOLUME = {3884},
PAGES = {571--583},
SERIES = {Lecture Notes in Computer Science},
ADDRESS = {Marseille, France},
ISBN = {3-540-32301-5},
}


Entry last modified by Uwe Brahm, 07/18/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)
Christine Kiesel
Created
02/06/2007 03:28:58 PM
Revisions
5.
4.
3.
2.
1.
Editor(s)
Uwe Brahm
Uwe Brahm
Uwe Brahm
Christine Kiesel
Christine Kiesel
Edit Dates
2007-07-18 14:45:45
07/07/2007 00:45:48
2007-04-26 18:52:39
06.02.2007 16:38:14
06.02.2007 16:35:22