# Simultaneous Approximations for Adversarial and Stochastic Online Budgeted Allocation

### Venue

Symposium on Discrete Algorithms (SODA), ACM/SIAM (2012)

### Publication Year

2012

### Authors

Vahab Mirrokni, Shayan Oveis Gharan, Morteza Zadimoghaddam

### BibTeX

## Abstract

Motivated by online ad allocation, we study the problem of simultaneous
approximations for the adversarial and stochastic online budgeted allocation
problem. This problem consists of a bipartite graph G = (X, Y, E), where the nodes
of Y along with their corresponding capacities are known beforehand to the
algorithm, and the nodes of X arrive online. When a node of X arrives, its incident
edges, and their respective weights are revealed, and the algorithm can match it to
a neighbor in Y. The objective is to maximize the weight of the final matching,
while respecting the capacities. When nodes arrive in an adversarial order, the
best competitive ratio is known to be 1 - 1/e, and it can be achieved by the
Ranking [18], and its generalizations (Balance [16, 21]). On the other hand, if the
nodes arrive through a random permutation, it is possible to achieve a competitive
ratio of 1 -- ε [9]. In this paper we design algorithms that achieve a competitive
ratio better than 1 -- 1/e on average, while preserving a nearly optimal worst case
competitive ratio. Ideally, we want to achieve the best of both worlds, i.e, to
design an algorithm with the optimal competitive ratio in both the adversarial and
random arrival models. We achieve this for unweighted graphs, but show that it is
not possible for weighted graphs. In particular, for unweighted graphs, under some
mild assumptions, we show that Balance achieves a competitive ratio of 1 -- ε in a
random permutation model. For weighted graphs, however, we prove this is not
possible; we prove that no online algorithm that achieves an approximation factor
of 1 -- 1/ε 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 preserving the competitive ratio of 1 -- 1/ε in the worst case. To this end,
we show the algorithm proposed by [21] achieves a competitive ratio of 0.76 for the
random arrival model, while having a 1 -- 1/ε ratio in the worst case.