Dependent Randomized Rounding for Matroid Polytopes and Applications

Details Dependent Randomized Rounding for Matroid Polytopes and Applications Dependent Randomized Rounding for Matroid Polytopes and Applications

2009-09-24

arxiv.org/abs/0909.4348v2

Computer Science

Data Structures and Algorithms

Rico Zenklusen joined as an author; paper substantially expanded compared to previous version; note a slight change in the tit

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Dependent Randomized Rounding for Matroid Polytopes and Applications does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Dependent Randomized Rounding for Matroid Polytopes and Applications, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dependent Randomized Rounding for Matroid Polytopes and Applications will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-424723