Beating Simplex for Fractional Packing and Covering Linear Programs

Details Beating Simplex for Fractional Packing and Covering Linear Programs Beating Simplex for Fractional Packing and Covering Linear Programs

2008-01-13

arxiv.org/abs/0801.1987v1

Computer Science

Data Structures and Algorithms

corrected version of FOCS 2007 paper: 48th Annual IEEE Symposium on Foundations of Computer Science, 2007, pp. 494-506

Scientific paper

We give an approximation algorithm for packing and covering linear programs (linear programs with non-negative coefficients). Given a constraint matrix with n non-zeros, r rows, and c columns, the algorithm (with high probability) computes feasible primal and dual solutions whose costs are within a factor of 1+eps of the optimal cost in time O(n+(r+c)log(n)/eps^2). For dense problems (with r,c=O(sqrt(n))) the time is O(n+sqrt(n)log(n)/eps^2) -- linear even as eps tends to zero. In comparison, previous Lagrangian-relaxation algorithms generally take at least Omega(n log(n)/eps^2) time, while (for small eps) the Simplex algorithm typically takes at least Omega(n min(r,c)) time.

Affiliated with

Also associated with

No associations

Rating

Beating Simplex for Fractional Packing and Covering Linear Programs 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 Beating Simplex for Fractional Packing and Covering Linear Programs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Beating Simplex for Fractional Packing and Covering Linear Programs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-633578