REAL TIME OPTIMIZATION IN NETWORKS: PRACTICAL ALGORITHMS WITH PROVABLE GUARANTEES

Abstract

We consider several optimization problems where the main challenge is to answer to a stream of requests. We provide algorithms that are efficient, practical, enjoy performance guarantees, and work well in practice. The first problem we study is computing Constrained Shortest Paths at scale. Even though the underlying optimization problem is NP-Hard, we can give parametric guarantees for the space requirement and running time of our algorithm. We use precomputation techniques, generalize the notion of Highway Dimension, and prove that, under mild conditions, we can scale Constrained Shortest Path whenever we can scale Shortest Path. We study also a large family of Resource Allocation and Pricing problems. We give a unified treatment and provide an algorithm that achieves constant regret, i.e., constant additive loss, in several problems. As special cases we can cover, we mention Online Packing (Network Revenue Management), Online Matching, Online Probing, and Pricing of Multiple Items. Our results hold even under several generalizations, such as restocking of resources and queues of customers with abandonment. Additionally, we present several robustness results in cases where the parameters of the problem are misspecified, similar to Bandits problems, or when there are two conflicting objectives, namely reward maximization and cost minimization. Furthermore, we also study the case when the arrival distribution can be accessed only via historical data and show that a single trace is enough to maintain constant regret guarantees.