Online Network Design with Outliers

In a classical online network design problem, traffic requirements are gradually revealed to an algorithm. Each time a new request arrives, the algorithm has to satisfy it by augmenting the network under construction in a proper way (with no possibility of recovery). In this paper we study a natural generalization of the problems above, where a fraction of the requests (the outliers) can be disregarded. Now, each time a request arrives, the algorithm first decides whether to satisfy it or not, and only in the first case it acts accordingly; in the end at least k out of t requests must be selected. We cast three classical network design problems into this framework, the Online Steiner Tree with Outliers, the Online TSP with Outliers, and the Online Facility Location with Outliers. We focus on the known distribution model, where terminals are independently sampled from a given distribution. For all the above problems, we present bicriteria online algorithms that, for any constant epsilon > 0, select at least (1-epsilon)k, terminals with high probability and pay in expectation O(log(2) n) times more than the expected cost of the optimal offline solution (selecting k terminals). These upper bounds are complemented by inapproximability results.