On the approximability of robust spanning tree problems
From MaRDI portal
Publication:620950
DOI10.1016/j.tcs.2010.10.006zbMath1206.90145MaRDI 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 complexity; combinatorial optimization; approximation; robust optimization; two-stage optimization
Related Items
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, Using the WOWA operator in robust discrete optimization problems, Compromise solutions for robust combinatorial optimization with variable-sized uncertainty, Robust two-stage combinatorial optimization problems under convex second-stage cost uncertainty, Combinatorial two-stage minmax regret problems under interval uncertainty, Two-stage combinatorial optimization problems under risk, The recoverable robust spanning tree problem with interval costs is polynomially solvable, Recoverable robust spanning tree problem under interval uncertainty representations, Robust recoverable and two-stage selection problems, The Robust (Minmax Regret) Quadratic Assignment Problem with Interval Flows
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
