6 citations · 13 across the 7 of their papers we have counts for
5 papers · 1 filter
Faster Submodular Maximization for Several Classes of Matroids
Monika Henzinger, Paul Liu, Jan Vondrak +1
The maximization of submodular functions have found widespread application in areas such as machine learning, combinatorial optimization, and economics, where practitioners often w…
On the Complexity of Sampling Redistricting Plans
Moses Charikar, Paul Liu, Tianyu Liu +1
A crucial task in the political redistricting problem is to sample redistricting plans i.e. a partitioning of the graph of census blocks into districts. We show that Recombination…
Streaming Submodular Maximization under Matroid Constraints
Moran Feldman, Paul Liu, Ashkan Norouzi-Fard +2
Recent progress in (semi-)streaming algorithms for monotone submodular function maximization has led to tight results for a simple cardinality constraint. However, current techniqu…
Improved Algorithms for Edge Colouring in the W-Streaming Model
Moses Charikar, Paul Liu
In the W-streaming model, an algorithm is given space and must process a large graph of up to edges. In this short note we give two algorithms fo…
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…