Traditionally, combinatorial optimization postulates that an input instance is given with absolute precision and certainty, and it aims at finding an optimum solution for the given instance. In contrast, real world input data are often uncertain, noisy, inaccurate. As a consequence, an optimum solution for a real world instance may not be meaningful or desired. While this unfortunate gap between theory and reality has been recognized for quite some time, it is far from understood, let alone resolved. We advocate to devote more attention to it, in order to develop algorithms that find meaningful solutions for uncertain inputs. We propose an approach towards this goal, and we show that this approach on the one hand creates a wealth of algorithmic problems, while on the other hand it appears to lead to good real world solutions.
展开▼
