AF: Small: Towards New Relaxations for Online Algorithms

We all are regularly asked to make decisions in the face of uncertainty: we decide how best to drive to work or how and at what prices to buy and sell things (everything from houses to groceries). And our computers make such choices as well to give good performance to their users: which order to process tasks q to maximize the throughput or minimize user delay, or which pages to keep in fast memory (because they will be accessed again soon) and which others moved to slower memory. These questions do not fall in the classical ``one-shot'' framework of computation, where an algorithm reads in the input, processes it and produces its output. Instead, they fall in the area of sequential decision-making, and specifically of online algorithms, which provides a framework in which we can formalize such questions and also reason about their solutions. For such problems, there is a natural tension between two competing desires: (a) to make decisions that maximize the instantaneous gratification but may be poor in the long run, or (b) to wait and maneuver into a good position to make gains in the future. This project aims to develop general-purpose algorithms that find optimal ways of hedging between these two extremes for a broad class of optimization problems in online optimization.

As an example, consider the k-server problem, which is a central problem in this area. In this, one controls k servers which move between some locations in a metric space. A sequence of requests arrives over time, where each request specifies a location, and one must move one of the servers from its current position to this requested location. The goal is to minimize the total server movement. Given a request, which server should be moved? As mentioned above, there is a tradeoff between being greedy and moving the servers closest to the requested location and moving more distant servers to be in a better position for future requests. Developing good algorithms for this and related problems has been a major challenge in the area. This project will investigate three ways of addressing the challenge: (a) To develop general principles for designing broadly-applicable algorithms for randomized settings, and in particular, to extend the classical work function algorithm (which is near-optimal for the deterministic setting) to randomized settings; (b) To get extendable, robust convex relaxations for k-server and its generalizations, and to use these relaxations to obtain good algorithms; (c) To develop a broader framework for typical instances, instead of focusing on the worst-case instances. Our work will draw on ideas from linear and convex optimization, stochastic optimization and optimal stopping theory, and online learning in order to deepen our understanding of these and other central questions in optimization under uncertainty.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

Award Number: 2608359
Principal Investigator: Anupam Gupta
Funds Obligated: $249,899
State: NY