MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Doerr, Benjamindblp
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
Conference URL::
Downloading URL:
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
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 15:28:58
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