## Invited Session Thu.3.H 3010

#### Thursday, 15:15 - 16:45 h, Room: H 3010

**Cluster 1: Approximation & online algorithms** [...]

### Online algorithms

**Chair: Lisa Fleischer**

**Thursday, 15:15 - 15:40 h, Room: H 3010, Talk 1**

**Aleksander Madry**

A polylogarithmic-competitive algorithm for the *k*-server problem

**Coauthors: Nikhil Bansal, Naor Buchbinder, Joseph Naor**

**Abstract:**

In this talk, we will consider one of the fundamental problems in online optimization: the *k*-server problem. This problem captures many online scenarios - in particular, the widely studied caching problem - and is considered by many to be the "holy grail'' problem of the field.

We will present a new randomized algorithm for the *k*-server problem that is the first online algorithm for this problem that achieves polylogarithmic competitiveness.

**Thursday, 15:45 - 16:10 h, Room: H 3010, Talk 2**

**Umang Bhaskar**

Online mixed packing and covering

**Coauthor: Lisa Fleischer**

**Abstract:**

In many problems, the inputs arrive over time, and must be dealt with irrevocably when they arrive. Such problems are *online* problems. A common method of solving online problems is to first solve the corresponding linear program online, and then round the fractional solution obtained. We give algorithms for solving mixed packing and covering linear programs, when the covering constraints arrive online. No prior sublinear competitive algorithms are known for this problem. We give the first such - a polylogarithmic-competitive algorithm for mixed packing and covering online. We also show a nearly tight lower bound.

We apply our techniques to solve two online fixed-charge problems with congestion, motivated by applications in machine scheduling and facility location. The linear program for these problems is more complicated than mixed packing and covering, and presents unique challenges. We show that our techniques combined with a randomized rounding procedure give polylogarithmic-competitive integral solutions. These problems generalize online set-cover, for which there is a polylogarithmic lower bound. Hence, our results are close to tight.

**Thursday, 16:15 - 16:40 h, Room: H 3010, Talk 3**

**Vahab Mirrokni**

Simultaneous adversarial and stochastic approximations for budgeted allocation problems

**Coauthors: Shayan Oveisgharan, Morteza Zadimoghaddam**

**Abstract:**

We study the problem of simultaneous approximations for the adversarial and stochastic online budgeted allocation problem: Consider a bipartite graph *G=(X,Y,E)*. When a node of *X* arrives online, the algorithm can match it to a neighbor in *Y*. The goal is to maximize the weight of the matching, while respecting the capacities. We seek algorithms that achieve very good competitive ratio on average while achieving an optimal ratio *1-1/e* in the worst case. For unweighted graphs, under some mild assumptions, we show an algorithm that achieves a competitive ratio of *1-ε* in the random permutation model. For weighted graphs, however, we prove this is not possible; we show that no online algorithm that achieves an approximation factor of *1-1/e* for the worst case inputs may achieve an average approximation factor better than 97.6,% for random inputs. In light of this hardness result, we aim to design algorithms with improved approximation ratios in the random arrival model while getting a *1-1/e* in the worst case.