Robust Selection Problems
摘要
Focussing on selection problems, we discuss the problem complexity and approximability for various combinations of decision criterion and uncertainty set. In particular, we show that there are some such combinations that result in a problem that can be solved in polynomial time.