93 citations · 155 across the 32 of their papers we have counts for
6 papers · 1 filter
Approximate and Strategyproof Maximin Share Allocation of Chores with Ordinal Preferences
Haris Aziz, Bo Li, Xiaowei Wu
We initiate the work on maximin share (MMS) fair allocation of m indivisible chores to n agents using only their ordinal preferences, from both algorithmic and mechanism design per…
Defending against Contagious Attacks on a Network with Resource Reallocation
Rufan Bai, Haoxing Lin, Xinyu Yang +3
In classic network security games, the defender distributes defending resources to the nodes of the network, and the attacker attacks a node, with the objective to maximize the dam…
Budget-feasible Maximum Nash Social Welfare Allocation is Almost Envy-free
Xiaowei Wu, Bo Li, Jiarui Gan
The Nash social welfare (NSW) is a well-known social welfare measurement that balances individual utilities and the overall efficiency. In the context of fair allocation of indivis…
Fully Online Matching II: Beating Ranking and Water-filling
Zhiyi Huang, Zhihao Gavin Tang, Xiaowei Wu +1
Karp, Vazirani, and Vazirani (STOC 1990) initiated the study of online bipartite matching, which has held a central role in online algorithms ever since. Of particular importance a…
A Simple 1-1/e Approximation for Oblivious Bipartite Matching
Zhihao Gavin Tang, Xiaowei Wu, Yuhao Zhang
We study the oblivious matching problem, which aims at finding a maximum matching on a graph with unknown edge set. Any algorithm for the problem specifies an ordering of the verte…
Dynamic Set Cover: Improved Amortized and Worst-Case Update Time
Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai +1
In the dynamic minimum set cover problem, a challenge is to minimize the update time while guaranteeing close to the optimal approximation factor. (Throughout,…