Randomized Rounding without Solving the Linear Program

Details Randomized Rounding without Solving the Linear Program Randomized Rounding without Solving the Linear Program

2002-05-18

arxiv.org/abs/cs/0205036v1

ACM-SIAM Symposium on Discrete Algorithms (1995)

Computer Science

Data Structures and Algorithms

Scientific paper

Randomized rounding is a standard method, based on the probabilistic method, for designing combinatorial approximation algorithms. In Raghavan's seminal paper introducing the method (1988), he writes: "The time taken to solve the linear program relaxations of the integer programs dominates the net running time theoretically (and, most likely, in practice as well)." This paper explores how this bottleneck can be avoided for randomized rounding algorithms for packing and covering problems (linear programs, or mixed integer linear programs, having no negative coefficients). The resulting algorithms are greedy algorithms, and are faster and simpler to implement than standard randomized-rounding algorithms. This approach can also be used to understand Lagrangian-relaxation algorithms for packing/covering linear programs: such algorithms can be viewed as as (derandomized) randomized-rounding schemes.

Affiliated with

Also associated with

No associations

Rating

Randomized Rounding without Solving the Linear Program 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 Randomized Rounding without Solving the Linear Program, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Randomized Rounding without Solving the Linear Program will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-599136