10 citations · 18 across the 6 of their papers we have counts for
10 papers
Minimum-Length Coordinated Motions For Two Convex Centrally-Symmetric Robots
David Kirkpatrick, Paul Liu
We study the problem of determining coordinated motions, of minimum total length, for two arbitrary convex centrally-symmetric (CCS) robots in an otherwise obstacle-free plane. Usi…
Dynamic Data Layout Optimization with Worst-case Guarantees
Kexin Rong, Paul Liu, Sarah Ashok Sonje +1
Many data analytics systems store and process large datasets in partitions containing millions of rows. By mapping rows to partitions in an optimized way, it is possible to improve…
Cardinality constrained submodular maximization for random streams
Paul Liu, Aviad Rubinstein, Jan Vondrak +1
We consider the problem of maximizing submodular functions in single-pass streaming and secretaries-with-shortlists models, both with random arrival order. For cardinality constrai…
Retrieving Top Weighted Triangles in Graphs
Raunak Kumar, Paul Liu, Moses Charikar +1
Pattern counting in graphs is a fundamental primitive for many network analysis tasks, and a number of methods have been developed for scaling subgraph counting to large graphs. Ma…
Submodular Optimization in the MapReduce Model
Paul Liu, Jan Vondrak
Submodular optimization has received significant attention in both practice and theory, as a wide array of problems in machine learning, auction theory, and combinatorial optimizat…
A sampling framework for counting temporal motifs
Paul Liu, Austin Benson, Moses Charikar
Pattern counting in graphs is fundamental to network science tasks, and there are many scalable methods for approximating counts of small patterns, often called motifs, in large gr…
Greedy and Local Ratio Algorithms in the MapReduce Model
Nicholas J. A. Harvey, Christopher Liaw, Paul Liu
MapReduce has become the de facto standard model for designing distributed algorithms to process big data on a cluster. There has been considerable research on designing efficient…
Approximation Schemes for Covering and Packing in the Streaming Model
Christopher Liaw, Paul Liu, Robert Reiss
The shifting strategy, introduced by Hochbaum and Maass, and independently by Baker, is a unified framework for devising polynomial approximation schemes to NP-Hard problems. This…
Characterizing minimum-length coordinated motions for two discs
David Kirkpatrick, Paul Liu
We study the problem of determining optimal coordinated motions for two disc robots in an otherwise obstacle-free plane. Using the total path length traced by the two disc centres…
A fast 25/6-approximation for the minimum unit disk cover problem
Paul Liu, Daniel Lu
Given a point set P in 2D, the problem of finding the smallest set of unit disks that cover all of P is NP-hard. We present a simple algorithm for this problem with an approximatio…