112 citations · 147 across the 10 of their papers we have counts for
Showing cs.DSShow all
3 papers · 1 filter
cs.DS2016
Matroid Online Bipartite Matching and Vertex Cover
Yajun Wang, Sam Chiu-wai Wong
The Adwords and Online Bipartite Matching problems have enjoyed a renewed attention over the past decade due to their connection to Internet advertising. Our community has contribu…
cs.DS2013
Online Vertex Cover and Matching: Beating the Greedy Algorithm
Yajun Wang, Sam Chiu-wai Wong
In this paper, we explicitly study the online vertex cover problem, which is a natural generalization of the well-studied ski-rental problem. In the online vertex cover problem, we…
cs.DS2011★ 2 cited
The Simulated Greedy Algorithm for Several Submodular Matroid Secretary Problems
Tengyu Ma, Bo Tang, Yajun Wang
We study the matroid secretary problems with submodular valuation functions. In these problems, the elements arrive in random order. When one element arrives, we have to make an im…