112 citations · 147 across the 10 of their papers we have counts for
Showing 2013Show all
2 papers · 1 filter
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.GT2013★ 5 cited
Sybil-proof Mechanisms in Query Incentive Networks
Wei Chen, Yajun Wang, Dongxiao Yu +1
In this paper, we study incentive mechanisms for retrieving information from networked agents. Following the model in [Kleinberg and Raghavan 2005], the agents are represented as n…