On the approximability of robust spanning tree problems
From MaRDI portal
Publication:620950
DOI10.1016/j.tcs.2010.10.006zbMath1206.90145OpenAlexW1523324024MaRDI QIDQ620950
Paweł Zieliński, Adam Kasperski
Publication date: 2 February 2011
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2010.10.006
computational complexitycombinatorial optimizationapproximationrobust optimizationtwo-stage optimization
Related Items (14)
The recoverable robust spanning tree problem with interval costs is polynomially solvable ⋮ Robust two-stage combinatorial optimization problems under convex second-stage cost uncertainty ⋮ Recoverable robust spanning tree problem under interval uncertainty representations ⋮ Robust recoverable and two-stage selection problems ⋮ Using the WOWA operator in robust discrete optimization problems ⋮ The Robust (Minmax Regret) Quadratic Assignment Problem with Interval Flows ⋮ On the complexity of robust multi-stage problems with discrete recourse ⋮ Approximating a two-machine flow shop scheduling under discrete scenario uncertainty ⋮ Combinatorial optimization problems with uncertain costs and the OWA criterion ⋮ Solution algorithms for unrelated machines minmax regret scheduling problem with interval processing times and the total flow time criterion ⋮ Robust combinatorial optimization under convex and discrete cost uncertainty ⋮ Combinatorial two-stage minmax regret problems under interval uncertainty ⋮ Compromise solutions for robust combinatorial optimization with variable-sized uncertainty ⋮ Two-stage combinatorial optimization problems under risk
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximation of min-max and min-max regret versions of some combinatorial optimization problems
- Commitment under uncertainty: Two-stage stochastic matching problems
- On the approximability of minmax (regret) network optimization problems
- Min-max and min-max regret versions of combinatorial optimization problems: A survey
- Robust discrete optimization and its applications
- A randomized algorithm for the min-Max selecting items problem with uncertain weights
- Two-stage stochastic matching and spanning tree problems: polynomial instances and approximation
- Hedging uncertainty: approximation algorithms for stochastic optimization problems
- A threshold of ln n for approximating set cover
- On the random 2-stage minimum spanning tree
- Approximating Single Machine Scheduling with Scenarios
- On Two-Stage Stochastic Minimum Spanning Trees
- Introduction to Stochastic Programming
- Free Bits, PCPs, and Nonapproximability---Towards Tight Results
- Pay Today for a Rainy Day: Improved Approximation Algorithms for Demand-Robust Min-Cut and Shortest Path Problems
This page was built for publication: On the approximability of robust spanning tree problems
