26 citations · 35 across the 7 of their papers we have counts for
8 papers
A constant factor approximation for Nash social welfare with subadditive valuations
Shahar Dobzinski, Wenzheng Li, Aviad Rubinstein +1
We present a constant-factor approximation algorithm for the Nash social welfare maximization problem with subadditive valuations accessible via demand queries. More generally, we…
Approximating Nash Social Welfare by Matching and Local Search
Jugal Garg, Edin Husić, Wenzheng Li +2
For any , we give a simple, deterministic -approximation algorithm for the Nash social welfare (NSW) problem under submodular valuations. We also co…
A constant-factor approximation algorithm for Nash Social Welfare with submodular valuations
Wenzheng Li, Jan Vondrák
We present a -approximation algorithm for the Nash Social Welfare problem with submodular valuations. Our algorithm builds on and extends a recent constant-factor approximatio…
Estimating the Nash Social Welfare for coverage and other submodular valuations
Wenzheng Li, Jan Vondrak
We study the Nash Social Welfare problem: Given agents with valuation functions , partition into so as to maximize $…
A polynomial lower bound on adaptive complexity of submodular maximization
Wenzheng Li, Paul Liu, Jan Vondrak
In large-data applications, it is desirable to design algorithms with a high degree of parallelization. In the context of submodular optimization, adaptive complexity has become a…
An Optimal Distributed -Coloring Algorithm?
Yi-Jun Chang, Wenzheng Li, Seth Pettie
Vertex coloring is one of the classic symmetry breaking problems studied in distributed computing. In this paper we present a new algorithm for -list coloring in the randomi…
The Energy Complexity of Broadcast
Yi-Jun Chang, Varsha Dani, Thomas P. Hayes +3
Energy is often the most constrained resource in networks of battery-powered devices, and as devices become smaller, they spend a larger fraction of their energy on communication (…
Distributed Edge Coloring with Small Palettes and a Special Case of the Constructive Lovász Local Lemma
Yi-Jun Chang, Qizheng He, Wenzheng Li +2
We explore the complexity of edge coloring in the LOCAL model in different palette size regimes. 1. Lower Bounds: First, we simplify the round elimination technique of Brandt et al…