Achieving Spatial Adaptivity while Finding Approximate Nearest Neighbors (2009)
Jonathan Derryberry, Don Sheehy, Daniel D. Sleator, Maverick Woo
We present the first spatially adaptive data structure that answers approximate nearest neighbor (ANN) queries to points that reside in a geometric space of any constant dimension d. The Lt-norm...
Confronting Hardness Using a Hybrid Approach ∗ (2008)
Virginia Vassilevska, Ryan Williams, Shan Leung, Maverick Woo
A hybrid algorithm is a collection of heuristics, paired with a polynomial time selector S that runs on the input to decide which heuristic should be executed to solve the problem. Hybrid algorithms...
Presented to The Academic Faculty (2006)
Abraham D. Flaxman, Alan Frieze, R. Ravi, Manuel Blum, Luis Von Ahn, Maverick Woo, ...
This thesis considers the average case analysis of algorithms, focusing primarily on NP-hard combinatorial optimization problems. It includes a catalog of distributions frequently used in...
Finger Search on Balanced Search Trees (2006)
This thesis introduces the concept of a heterogeneous decomposition of a balanced search tree and apply it to the following problems: • How can finger search be implemented without changing the...
Finding effective support-tree preconditioners (2005)
Bruce M. Maggs, Gary L. Miller, Ojas Parekh, R. Ravi, Shan Leung, Maverick Woo
In 1995, Gremban, Miller, and Zagha introduced support-tree preconditioners and a parallel algorithm called support-tree conjugate gradient (STCG) for solving linear systems of the form Ax = b, where...
Confronting hardness using a hybrid approach (2005)
Virginia Vassilevska, Ryan Williams, Shan Leung, Maverick Woo
combinatorial optimization A hybrid algorithm is a collection of heuristics, paired with a polynomial time selector S that runs on the input to decide which heuristic should be executed to solve the...
Confronting hardness using a hybrid approach (2005)
Virginia Vassilevska, Ryan Williams, Shan Leung, Maverick Woo
1 Introduction Motivation. Ever since the foundation of NP-completeness was laid down by Cook, Levin and other pioneers in the 1970s, our community has devised a number of algorithmic strategies to...
Space-efficient finger search on degree-balanced search trees (2003)
Guy E. Blelloch, Bruce M. Maggs, Shan Leung, Maverick Woo
We show how to support the finger search operation on degree-balanced search trees in a space-efficient manner that retains a worst-case time bound of O(log d), where d is the difference in rank...
Space-efficient finger search on degree-balanced search trees (2003)
Guy E. Blelloch, Bruce M. Maggs, Shan Leung, Maverick Woo
An extended abstract of this paper has appeared in ACM-SIAM Symposium on Discrete Algorithms (SODA) 2003. This paper was last revised on April 15, 2003. We show how to support the finger search...
Space-efficient finger search on degree-balanced search trees (2003)
Guy E. Blelloch, Bruce M. Maggs, Shan Leung, Maverick Woo
We show how to support the finger search operation on degree-balanced search trees in a space-efficient manner that retains a worst-case time bound of O(log d), where d is the difference in rank...
Solving symmetric diagonally-dominant systems by preconditioning. Unpublished manuscript (2002)
Bruce M. Maggs, Gary L. Miller, Ojas Parekh, R. Ravi, Shan Leung, Maverick Woo
In this paper we design support-tree preconditioners for n × n matrices with m nonzeros that are symmetric and diagonally-dominant with a nonnegative diagonal (SDD matrix). This reduces to designing...