Please help transcribe this video using our simple transcription tool. You need to be logged in to do so.

Description

We consider the problem of randomly rounding a fractional solution $x$ in a polytope $P subset RR^n$ to a vertex $X$ of $P$, so that $E[X] = x$. Our goal is to achieve {em concentration properties} for linear and submodular 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 new {em swap rounding} technique which can be applied in a variety of settings including {em matroids}, {em matroid intersection} and {em non-bipartite graph $b$-matchings}, while providing Chernoff-type concentration bounds for linear and submodular functions of the rounded solution. In addition to existing techniques based on negative correlation, we use martingale methods to obtain an exponential tail estimate for monotone submodular functions, and also for linear functions in settings where negative correlation does not hold. The rounding scheme explicitly exploits {em exchange properties} of the underlying combinatorial structures, and highlights these properties as the basis for concentration bounds.

The framework of matroids and matroid intersection provides a unifying scheme for several known applications cite{GKPS06,KMPS09,CCPV09,KST09,AGMGS10} as well as new ones, and its flexibility allows a richer set of constraints to be incorporated easily. We illustrate this on the max-min allocation problem with submodular valuations, submodular maximization subject to a matroid and multiple linear constraints, the crossing spanning tree problem, and resource allocation / broadcast scheduling problems with various demand/capacity constraints.

Questions and Answers

You need to be logged in to be able to post here.