Simultaneous approximations for adversarial and stochastic online budgeted allocation

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