Monika Henzinger

most citedOnline Stochastic Packing Applied to Display Ad Allocation

39 citations · 39 across the 3 of their papers we have counts for

collaborators

Showing cs.DSShow all

3 papers · 1 filter

cs.DS2014

Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching

Sayan Bhattacharya, Monika Henzinger, Giuseppe F. Italiano

We present the first deterministic data structures for maintaining approximate minimum vertex cover and maximum matching in a fully dynamic graph $G = (V, E)$ , with $∣ V ∣ = n$ and $|…

cs.DS2014

Online Bipartite Matching with Decomposable Weights

Moses Charikar, Monika Henzinger, Huy L. Nguyen

We study a weighted online bipartite matching problem: $G (V_{1}, V_{2}, E)$ is a weighted bipartite graph where $V_{1}$ is known beforehand and the vertices of $V_{2}$ arrive online. The g…

cs.DS2010★ 39 cited

Online Stochastic Packing Applied to Display Ad Allocation

Jon Feldman, Monika Henzinger, Nitish Korula +2

Inspired by online ad allocation, we study online stochastic packing linear programs from theoretical and practical standpoints. We first present a near-optimal online algorithm fo…