Improved approximations for robust mincut and shortest path

Details Improved approximations for robust mincut and shortest path Improved approximations for robust mincut and shortest path

2010-10-14

arxiv.org/abs/1010.2885v1

Computer Science

Data Structures and Algorithms

Scientific paper

In two-stage robust optimization the solution to a problem is built in two stages: In the first stage a partial, not necessarily feasible, solution is exhibited. Then the adversary chooses the "worst" scenario from a predefined set of scenarios. In the second stage, the first-stage solution is extended to become feasible for the chosen scenario. The costs at the second stage are larger than at the first one, and the objective is to minimize the total cost paid in the two stages. We give a 2-approximation algorithm for the robust mincut problem and a ({\gamma}+2)-approximation for the robust shortest path problem, where {\gamma} is the approximation ratio for the Steiner tree. This improves the factors (1+\sqrt2) and 2({\gamma}+2) from [Golovin, Goyal and Ravi. Pay today for a rainy day: Improved approximation algorithms for demand-robust min-cut and shortest path problems. STACS 2006]. In addition, our solution for robust shortest path is simpler and more efficient than the earlier ones; this is achieved by a more direct algorithm and analysis, not using some of the standard demand-robust optimization techniques.

Affiliated with

Also associated with

No associations

Rating

Improved approximations for robust mincut and shortest path 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 Improved approximations for robust mincut and shortest path, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Improved approximations for robust mincut and shortest path will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-285460