We propose a novel approach for optimization under uncertainty. Our approach does not assume any particular noise model behind the measurements, and only requires two typical instances. We first propose a measure of similarity of instances (with respect to a given objective). Based on this measure, we then choose a solution randomly among all solutions that are near-optimum for both instances. The exact notion of near-optimum is intertwined with the proposed similarity measure. Our similarity measure also allows us to derive formal statements about the expected quality of the computed solution. Furthermore, we apply our approach to various optimization problems.

Given an urban public transportation network and historic delay information, we consider the problem of computing reliable journeys. We propose new algorithms based on our recently presented solution concept (Böhmová et al., ATMOS 2013), and perform an experimental evaluation using real-world delay data from Zürich, Switzerland. We compare these methods to natural approaches as well as to our recently proposed method which can also be used to measure typicality of past observations. Moreover, we demonstrate how this measure relates to the predictive quality of the individual methods. In particular, if the past observations are typical, then the learning- based methods are able to produce solutions that perform well on typical days, even in the presence of large delays.