Google Inc., Mountain View, CA 94043, USA
Jie Gao, Leonidas J. Guibas, John Hershberger, Li Zhang, An Zhu
Proceedings of the 2nd ACM Interational Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc 2001, 2001 – MobiHoc
We propose a new routing graph, the Restricted Delaunay Graph (RDG), for ad hoc networks. Combined with a node clustering algorithm RDG can be used as an underlying graph for geographic routing protocols. This graph has the following attractive ...
Jie Gao, Leonidas J. Guibas, John Hershberger, Li Zhang, An Zhu
Computational Geometry 2001, 2001 – SoCG
\emph{We propose a new randomized algorithm for maintaining a set of c lusters among moving nodes in the plane. Given a specified cluster radius, our algorithm selects and maintains a variable subset of the nodes as cluster centers. This subset has ...
Gagan Aggarwal, Tomás Feder, Krishnaram Kenthapadi, Samir Khuller, Rina Panigrahy, Dilys Thomas, An Zhu
Twenty-Fifth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2006 – PODS
Publishing data for analysis from a table containing personal records, while maintaining individual privacy, is a problem of increasing importance today. The traditional approach of de-identifying records is to remove identifying fields such as ...
Chandra Chekuri, Sanjeev Khanna, An Zhu
We study the problem of minimizing weighted flow time on a single machine in the preemptive setting. We present an O(\log^2 P)-competitive semi-online algorithm where P is the ratio of the maximum and minimum processing times of jobs in the system. ...
Nir Andelman, Yishay Mansour, An Zhu
SODA 2003: Baltimore, 2003 – SODA
o&quot; &quot; for two values and \Theta (log o&quot;&quot;) for multiple values. Inaddition we improve the previous known lower and upper bounds of the Fixed Partition and Flexible Partition policies. For the FIFO ...
Gagan Aggarwal, Tomás Feder, Rajeev Motwani, An Zhu
Automata, Languages and Programming: 31st International Colloquium, ICALP 2004, vol. 3142,2004 – ICALP
Abstract. In the information age, the availability of data on consumer profiles has opened new possibilities for companies to increase their revenue via data mining techniques. One approach has been to strategically set prices of various products, ...
Jie Gao, Leonidas J. Guibas, John Hershberger, Li Zhang, An Zhu
Discrete & Computational Geometry, vol. 30,no. 1,2003 – DCG
We propose a new randomized algorithm for maintaining a set of clusters among moving nodes in the plane. Given a specified cluster radius, our algorithm selects and maintains a variable subset of the nodes as cluster centers. This subset has the ...
Gagan Aggarwal, Rajeev Motwani, An Zhu
SPAA 2003: Proceedings of the Fifteenth Annual ACM Symposium on Parallel Algorithms, 2003 – SPAA
In the classical load balancing or multiprocessor scheduling problem, we are given a sequence of jobs of varying sizes and are asked to assign each job to one of the m empty processors. A typical objective is to minimize makespan, the load on the ...