Non-independent Randomized Rounding

Benjamin Doerr

Non-independent Randomized Rounding

Benjamin Doerr

Christian-Albrechts-University Kiel

Résultats de recherche: Contribution à une conférence › Papier › Revue par des pairs

Résumé

We investigate an extension of the randomized rounding technique introduced by Raghavan and Thompson. Whereas their approach only requires that each variable is rounded with probabilities given by its fractional part, we also impose this condition on several sums of variables. Thus in particular our roundings are not independent. We show that such non-independent randomized roundings exist if and only if the hypergraph corresponding to these dependencies is totally unimodular.

langue originale	Anglais
Pages	568-569
Nombre de pages	2
état	Publié - 15 avr. 2004
Modification externe	Oui
Evénement	Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms - New Orleans, LA., États-Unis Durée: 11 janv. 2004 → 13 janv. 2004

Une conférence

Une conférence	Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms
Pays/Territoire	États-Unis
La ville	New Orleans, LA.
période	11/01/04 → 13/01/04

Autres fichiers et liens

Lien vers la publication dans Scopus

Contient cette citation

@conference{a3f2ba0cfa064e20a82d84da88dbbb58,

title = "Non-independent Randomized Rounding",

abstract = "We investigate an extension of the randomized rounding technique introduced by Raghavan and Thompson. Whereas their approach only requires that each variable is rounded with probabilities given by its fractional part, we also impose this condition on several sums of variables. Thus in particular our roundings are not independent. We show that such non-independent randomized roundings exist if and only if the hypergraph corresponding to these dependencies is totally unimodular.",

author = "Benjamin Doerr",

year = "2004",

month = apr,

day = "15",

language = "English",

pages = "568--569",

note = "Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms ; Conference date: 11-01-2004 Through 13-01-2004",

}

TY - CONF

T1 - Non-independent Randomized Rounding

AU - Doerr, Benjamin

PY - 2004/4/15

Y1 - 2004/4/15

N2 - We investigate an extension of the randomized rounding technique introduced by Raghavan and Thompson. Whereas their approach only requires that each variable is rounded with probabilities given by its fractional part, we also impose this condition on several sums of variables. Thus in particular our roundings are not independent. We show that such non-independent randomized roundings exist if and only if the hypergraph corresponding to these dependencies is totally unimodular.

AB - We investigate an extension of the randomized rounding technique introduced by Raghavan and Thompson. Whereas their approach only requires that each variable is rounded with probabilities given by its fractional part, we also impose this condition on several sums of variables. Thus in particular our roundings are not independent. We show that such non-independent randomized roundings exist if and only if the hypergraph corresponding to these dependencies is totally unimodular.

UR - https://www.scopus.com/pages/publications/1842592000

M3 - Paper

AN - SCOPUS:1842592000

SP - 568

EP - 569

T2 - Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 11 January 2004 through 13 January 2004

ER -

Non-independent Randomized Rounding

Résumé

Une conférence

Autres fichiers et liens

Empreinte digitale

Contient cette citation