Generating Randomized Roundings with Cardinality Constraints and 
Derandomizations

Doerr, Benjamin; Durand, Bruno; Thomas, Wolfgang

Datensatz

DATENSATZ AKTIONENEXPORT

Zur Ablage hinzufügen

Lokale TagsFreigabegeschichteDetailsÜbersicht

Freigegeben

Konferenzbeitrag

Generating Randomized Roundings with Cardinality Constraints and Derandomizations

MPG-Autoren

/persons/resource/persons44338

Doerr, Benjamin
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen

Es sind keine externen Ressourcen hinterlegt

Volltexte (beschränkter Zugriff)

Für Ihren IP-Bereich sind aktuell keine Volltexte freigegeben.

Volltexte (frei zugänglich)

Es sind keine frei zugänglichen Volltexte in PuRe verfügbar

Ergänzendes Material (frei zugänglich)

Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar

Zitation

Doerr, B. (2006). Generating Randomized Roundings with Cardinality Constraints and Derandomizations. In STACS 2006, 23rd Annual Symposium on Theoretical Aspects of Computer Science (pp. 571-583). Berlin, Germany: Springer.

Zitierlink: https://hdl.handle.net/11858/00-001M-0000-000F-22F7-0

Zusammenfassung

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.