  Motivated by several applications, we consider the problem of randomly
rounding a fractional solution in a matroid (base) polytope to an integral one.
We consider the pipage rounding technique and also present a new technique,
randomized swap rounding. Our main technical results are concentration bounds
for functions of random variables arising from these rounding techniques. We
prove Chernoff-type concentration bounds for linear functions of random
variables arising from both techniques, and also a lower-tail exponential bound
for monotone submodular functions of variables arising from randomized swap
rounding.
  The following are examples of our applications: (1) We give a
(1-1/e-epsilon)-approximation algorithm for the problem of maximizing a
monotone submodular function subject to 1 matroid and k linear constraints, for
any constant k and epsilon>0. (2) We present a result on minimax packing
problems that involve a matroid base constraint. We give an O(log m / log log
m)-approximation for the general problem Min {lambda: x \in {0,1}^N, x \in
B(M), Ax <= lambda b}, where m is the number of packing constraints. (3) We
generalize the continuous greedy algorithm to problems involving multiple
submodular functions, and use it to find a (1-1/e-epsilon)-approximate pareto
set for the problem of maximizing a constant number of monotone submodular
functions subject to a matroid constraint. An example is the Submodular Welfare
Problem where we are looking for an approximate pareto set with respect to
individual players' utilities.
