Non-independent randomized rounding

Benjamin Doerr

Non-independent randomized rounding

Benjamin Doerr

Christian-Albrechts-University Kiel

Research output: Contribution to conference › Paper › peer-review

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.

Original language	English
Pages	506-507
Number of pages	2
Publication status	Published - 1 Jan 2003
Externally published	Yes
Event	Configuralble Computing: Technology and Applications - Boston, MA, United States Duration: 2 Nov 1998 → 3 Nov 1998

Conference

Conference	Configuralble Computing: Technology and Applications
Country/Territory	United States
City	Boston, MA
Period	2/11/98 → 3/11/98

Cite this

@conference{ab17750095c540608ed7cac0dcd6ab9b,

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 = "2003",

month = jan,

day = "1",

language = "English",

pages = "506--507",

note = "Configuralble Computing: Technology and Applications ; Conference date: 02-11-1998 Through 03-11-1998",

}

TY - CONF

T1 - Non-independent randomized rounding

AU - Doerr, Benjamin

PY - 2003/1/1

Y1 - 2003/1/1

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/0037739963

M3 - Paper

AN - SCOPUS:0037739963

SP - 506

EP - 507

T2 - Configuralble Computing: Technology and Applications

Y2 - 2 November 1998 through 3 November 1998

ER -

Non-independent randomized rounding

Abstract

Conference

Other files and links

Fingerprint

Cite this