publication . Other literature type . Conference object . 2010

Dependent Randomized Rounding via Exchange Properties of Combinatorial Structures

Chandra Chekuri; Jan Vondrak; Rico Zenklusen;
  • Published: 01 Oct 2010
  • Publisher: Institute of Electrical and Electronics Engineers (IEEE)
We consider the problem of randomly rounding a fractional solution $x$ in an integer polytope $P \subseteq [0,1]^n$ to a vertex $X$ of $P$, so that $\E[X] = x$. Our goal is to achieve {\em concentration properties} for linear and sub modular functions of the rounded solution. Such dependent rounding techniques, with concentration bounds for linear functions, have been developed in the past for two polytopes: the assignment polytope (that is, bipartite matchings and $b$-matchings)~\cite{S01, GKPS06, KMPS09}, and more recently for the spanning tree polytope~\cite{AGMGS10}. These schemes have led to a number of new algorithmic results. In this paper we describe a n...
Powered by OpenAIRE Research Graph
Any information missing or wrong?Report an Issue