Anzeige
Erschienen in:
2006 | OriginalPaper | Buchkapitel
Generating Randomized Roundings with Cardinality Constraints and Derandomizations
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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
$\tilde{O}(|V|)$
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
(
mn
log
n
) time algorithm that works in the RAM model for arbitrary matrices with entries in ℚ
≥ 0
. This improves over the
O
(
mn
2
log(
mn
)) time solution of Srivastav and Stangier.