6 citations · 13 across the 7 of their papers we have counts for
9 papers
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…
Coordinated Motion Planning Through Randomized k-Opt
Paul Liu, Jack Spalding-Jamieson, Brandon Zhang +1
This paper examines the approach taken by team gitastrophe in the CG:SHOP 2021 challenge. The challenge was to find a sequence of simultaneous moves of square robots between two gi…
An Elo-like System for Massive Multiplayer Competitions
Aram Ebtekar, Paul Liu
Rating systems play an important role in competitive sports and games. They provide a measure of player skill, which incentivizes competitive performances and enables balanced matc…
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 simple bipartite graph projection model for clustering in networks
Austin R. Benson, Paul Liu, Hao Yin
Graph datasets are frequently constructed by a projection of a bipartite graph, where two nodes are connected in the projection if they share a common neighbor in the bipartite gra…
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…
SYM-ILDL: Incomplete Factorization of Symmetric Indefinite and Skew-Symmetric Matrices
Chen Greif, Shiwen He, Paul Liu
SYM-ILDL is a numerical software package that computes incomplete (or `ILDL') factorizations of symmetric indefinite and real skew-symmetric matrices. The core of the alg…