112 citations · 147 across the 10 of their papers we have counts for
10 papers
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…
Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Arms
Wei Chen, Yajun Wang, Yang Yuan +1
We define a general framework for a large class of combinatorial multi-armed bandit (CMAB) problems, where subsets of base arms with unknown distributions form super arms. In each…
Minimizing Seed Set Selection with Probabilistic Coverage Guarantee in a Social Network
Peng Zhang, Wei Chen, Xiaoming Sun +2
A topic propagating in a social network reaches its tipping point if the number of users discussing it in the network exceeds a critical threshold such that a wide cascade on the t…
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…
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…
Influence Diffusion Dynamics and Influence Maximization in Social Networks with Friend and Foe Relationships
Yanhua Li, Wei Chen, Yajun Wang +1
Influence diffusion and influence maximization in large-scale online social networks (OSNs) have been extensively studied, because of their impacts on enabling effective online vir…
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…
Information Dissemination via Random Walks in d-Dimensional Space
Henry Lam, Zhenming Liu, Michael Mitzenmacher +2
We study a natural information dissemination problem for multiple mobile agents in a bounded Euclidean space. Agents are placed uniformly at random in the -dimensional space $\{…
Optimal Pricing in Social Networks with Incomplete Information
Wei Chen, Pinyan Lu, Xiaorui Sun +3
In revenue maximization of selling a digital product in a social network, the utility of an agent is often considered to have two parts: a private valuation, and linearly additive…
Permanents of Circulants: a Transfer Matrix Approach (Expanded Version)
Mordecai J. Golin, Yiu Cho Leung, Yajun Wang
Calculating the permanent of a (0,1) matrix is a #P-complete problem but there are some classes of structured matrices for which the permanent is calculable in polynomial time. The…