Dependent randomized rounding via exchange properties of combinatorial structures

Abstract

We consider the problem of randomly rounding a fractional solution x in an integer polytope P ⊆ [0, 1]n to a vertex X of P, so that E[X] = x. Our goal is to achieve 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) [32], [19], [23], and more recently for the spanning tree polytope [2]. These schemes have led to a number of new algorithmic results. In this paper we describe a new swap rounding technique which can be applied in a variety of settings including matroids and matroid intersection, 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 a martingale argument to obtain an exponential tail estimate for monotone submodular functions. The rounding scheme explicitly exploits exchange properties of the underlying combinatorial structures, and highlights these properties as the basis for concentration bounds. Matroids and matroid intersection provide a unifying framework for several known applications [19], [23], [7], [22], [2] as well as new ones, and their generality allows a richer set of constraints to be incorporated easily. We give some illustrative examples, with a more comprehensive discussion deferred to a later version of the paper. © 2010 IEEE.