On the approximability of robust spanning tree problems

Details On the approximability of robust spanning tree problems On the approximability of robust spanning tree problems

2010-04-16

arxiv.org/abs/1004.2891v1

Computer Science

Computational Complexity

Scientific paper

In this paper the minimum spanning tree problem with uncertain edge costs is discussed. In order to model the uncertainty a discrete scenario set is specified and a robust framework is adopted to choose a solution. The min-max, min-max regret and 2-stage min-max versions of the problem are discussed. The complexity and approximability of all these problems are explored. It is proved that the min-max and min-max regret versions with nonnegative edge costs are hard to approximate within $O(\log^{1-\epsilon} n)$ for any $\epsilon>0$ unless the problems in NP have quasi-polynomial time algorithms. Similarly, the 2-stage min-max problem cannot be approximated within $O(\log n)$ unless the problems in NP have quasi-polynomial time algorithms. In this paper randomized LP-based approximation algorithms with performance ratio of $O(\log^2 n)$ for min-max and 2-stage min-max problems are also proposed.

Affiliated with

Also associated with

No associations

Rating

On the approximability of robust spanning tree problems 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 On the approximability of robust spanning tree problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the approximability of robust spanning tree problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-624460