Paper Info
Title
Simultaneous approximations for adversarial and stochastic online budgeted allocation
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.
Year
DOI
Venue
2012
10.5555/2095116.2095250
SODA
Keywords
Field
DocType
weighted graph,competitive ratio,simultaneous approximation,random permutation,stochastic online,random permutation model,improved approximation ratio,unweighted graph,worst case,random arrival model,random input,optimal competitive ratio
Discrete mathematics,Online algorithm,Graph,Mathematical optimization,Combinatorics,Ranking,Generalization,Computer science,Bipartite graph,Random permutation,Adversarial system,Competitive analysis
Conference
ISBN
Citations 
PageRank 
978-1-61197-251-1
19
0.89
References 
Authors
25
3
Name
Order
Citations
PageRank
VAHAB S. MIRROKNI14309287.14
Shayan Oveis Gharan232326.63
Morteza Zadimoghaddam338234.40