Name
Abstract | ||
|---|---|---|
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^-^@en) for any @e0 unless the problems in NP have quasi-polynomial time algorithms. Similarly, the 2-stage min-max problem cannot be approximated within O(logn) unless the problems in NP have quasi-polynomial time algorithms. In this paper randomized LP-based approximation algorithms with performance bound of O(log^2n) for min-max and 2-stage min-max problems are also proposed. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1016/j.tcs.2010.10.006 | Clinical Orthopaedics and Related Research |
Keywords | DocType | Volume |
2-stage min-max version,computational complexity,two-stage optimization,discrete scenario set,2-stage min-max problem,approximation algorithm,robust optimization,nonnegative edge cost,quasi-polynomial time algorithm,combinatorial optimization,tree problem,approximation,problems are also proposed. keywords: combinatorial optimization,min-max regret,min-max regret version,uncertain edge cost,minimum spanning tree,spanning tree | Journal | 412 |
Issue | ISSN | Citations |
4-5 | Theoretical Computer Science | 13 |
PageRank | References | Authors |
0.61 | 18 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Adam Kasperski | 1 | 352 | 33.64 |
| Pawe Zieliski | 2 | 13 | 0.61 |