3 citations · 3 across the 3 of their papers we have counts for
5 papers
Obtaining Approximately Optimal and Diverse Solutions via Dispersion
Jie Gao, Mayank Goswami, Karthik C. S. +3
There has been a long-standing interest in computing diverse solutions to optimization problems. Motivated by reallocation of governmental institutions in Sweden, in 1995 J. Krarup…
Streaming Complexity of Spanning Tree Computation
Yi-Jun Chang, Martin Farach-Colton, Tsan-Sheng Hsu +1
The semi-streaming model is a variant of the streaming model frequently used for the computation of graph problems. It allows the edges of an -node input graph to be read sequen…
Streaming Algorithms for Planar Convex Hulls
Martin Farach-Colton, Meng Li, Meng-Tsung Tsai
Many classical algorithms are known for computing the convex hull of a set of point in using space. For large point sets, whose size exceeds the size of t…
Optimal Ball Recycling
Michael A. Bender, Jake Christensen, Alex Conway +3
Balls-and-bins games have been a wildly successful tool for modeling load balancing problems. In this paper, we study a new scenario, which we call the ball recycling game, defined…
On the complexity of computing prime tables
Martin Farach-Colton, Meng-Tsung Tsai
Many large arithmetic computations rely on tables of all primes less than . For example, the fastest algorithms for computing takes time , where $M(n)…