|
Publications grouped by
topic
|
|
- Near-Optimal
Algorithms for Unique Games
with Konstantin Makarychev and Yury Makarychev,
to appear in Proceedings of
the 38th ACM Symposium on Theory of Computing (2006).
- New
Approximation Guarantees for Chromatic Number
with Sanjeev Arora and Eden Chlamtac,
to appear in Proceedings of the 38th ACM
Symposium on Theory of Computing (2006).
- Ferret:
A Toolkit for Content-Based Similarity Search
with Christine Lv, William
Josephson, Zhe Wang and Kai Li,
to
appear in Proceedings of ACM SIGOS EuroSys Conference (2006).
- l22
spreading metrics for vertex ordering problems
with MohammadTaghi
Hajiaghayi, Howard Karloff and Satish Rao
in Proceedings of the 17th
ACM-SIAM Symposium on Discrete
Algorithms (2006).
- Directed
Metrics and Directed Graph Partitioning Problems
with Konstantin Makarychev and Yury Makarychev
in Proceedings of the 17th
ACM-SIAM Symposium on Discrete
Algorithms (2006).
- A
Robust Maximum Completion Time Measure for Scheduling
with Samir Khuller,
in Proceedings of the 17th
ACM-SIAM Symposium on Discrete
Algorithms (2006).
- Fitting
tree metrics: Hierarchical Clustering and Phylogeny
with Nir Ailon,
in Proceedings of the 46th Annual IEEE Symposium on Foundations of
Computer Science (2005).
- Sampling
Bounds for Stochastic Optimization
with
Chandra Chekuri and
Martin Pal,
in Proceedings of APPROX-RANDOM (2005).
- O(sqrt{log
n}) approximation algorithms for Min UnCut, Min 2CNF Deletion, and
directed cut problems
with Amit Agarwal, Konstantin Makarychev, Yury
Makarychev,
in Proceedings of the 37th ACM Symposium on Theory of
Computing (2005).
- Aggregating
Inconsistent Information: Ranking and Clustering
with Nir Ailon and Alantha Newman,
in Proceedings of the 37th ACM Symposium on Theory of
Computing (2005).
- On
Non-uniform Multicommodity Buy-at-Bulk Network Design
with Adriana Karagiozova,
in Proceedings of the 37th ACM Symposium on Theory of
Computing (2005).
- A
Tight Threshold for Metric Ramsey Phenomena
with Adriana Karagiozova,
in Proceedings of the 16th ACM-SIAM Symposium on Discrete
Algorithms (2005).
- Approximation
the Average Response Time in Broadcast Scheduling
with Nikhil Bansal, Sanjeev Khanna and Seffi Naor,
in Proceedings of the 16th ACM-SIAM Symposium on Discrete
Algorithms (2005).
- Image
Similarity Search with Compact Data Structures
with Qin Lv and Kai Li,
in Proceedings of the ACM Conference on Information and
Knowledge Management (CIKM 2004).
- On the
Advantage of Network Coding for Improving Network Throughput
with Amit Agarwal,
in Proceedings of the IEEE Information Theory Workshop
(2004).
- Maximizing quadratic programs: extending
Grothendieck's inequality
with Anthony Wirth,
in Proceedings of the 45th Annual IEEE Symposium on
Foundations of Computer Science (2004).
- On the Integrality Ratio for Asymmetric TSP
with Michel X. Goemans and Howard Karloff,
in Proceedings of the 45th Annual IEEE Symposium on
Foundations of Computer Science (2004).
- On
the Impossibility of Dimension Reduction in l1
with Bo Brinkman,
in Proceedings of the 44th Annual IEEE Symposium on Foundations of
Computer Science (2003), best paper award.
- Clustering
with Qualitative Information,
with Venkatesan Guruswami and Anthony Wirth,
in Proceedings of the 44th Annual IEEE Symposium on
Foundations of Computer Science (2003).
- Better
Streaming Algorithms for Clustering Problems,
with L. O'Callaghan and R. Panigrahy,
in Proceedings of the 35th Annual ACM Symposium on Theory of
Computing, (2003).
- Dimension
Reduction in the l1 norm,
with A. Sahai,
in Proceedings of the 43rd Annual IEEE Conference on
Foundations of Computer Science (2002).
- New
Algorithms for Subset Query, Partial Match, Orthogonal Range Searching
and Related Problems,
with P. Indyk and R. Panigrahy,
in Proceedings of the 29th International Colloquium on
Automata Languages and Programming, (2002).
- Finding
Frequent Items in Data Streams,
with K. Chen and M. Farach-Colton,
in Proceedings of the 29th International Colloquium on
Automata Languages and Programming, (2002).
- Similarity
Estimation Techniques from Rounding Algorithms,
in Proceedings of the 34th Annual ACM Symposium on Theory
of Computing, (2002).
- Approximating
The Smallest Grammar: Kolmogorov Complexity in Natural Models,
with E. Lehman, D. Liu, R. Panigrahy, M. Prabhakaran, A. Rasala, A.
Sahai, and A. Shelat,
in Proceedings of the 34th Annual ACM Symposium on Theory
of Computing, (2002).
- On
Semidefinite Programming Relaxations for Graph Coloring and Vertex
Cover,
in Proceedings of the 13th Annual ACM-SIAM Symposium on
Discrete Algorithms, (2002).
- Clustering
to Minimize the Sum of Cluster Diameters,
with R. Panigrahy,
in Proceedings of the 33rd Annual ACM Symposium on Theory
of Computing, (2001).
- Approximating
Min-Sum k-Clustering in Metric Spaces,
with Y. Bartal and D. Raz,
in Proceedings of the 33rd Annual ACM Symposium on Theory
of Computing, (2001).
- Algorithms
for Facility Location with Outliers,
with S. Khuller, D. Mount and G. Narasimhan,
in Proceedings of the 12th Annual ACM-SIAM Symposium on
Discrete Algorithms, (2001).
- Combinatorial
Feature Selection Problems,
with V. Guruswami, S. Rajagopalan, S. Ravikumar and A. Sahai,
in Proceedings of the 41st Annual IEEE Conference on
Foundations of Computer Science, (2000).
- Resource
Optimization in QoS Multicast Routing of Real-Time Multimedia
with J. Naor and B. Schieber,
in Proceedings of the 19th Annual IEEE INFOCOM (2000).
- Greedy
Approximation Algorithms for Finding Dense Components in Graphs,
in Proceedings of APPROX, (2000).
- Minimum Outage Transmission
over Fading Channels with Delay Constraint,
with R. Negi and J. Cioffi,
in Proceedings of the IEEE International Conference on
Communication, (2000).
- Query
Strategies for Priced Information,
with R. Fagin, V. Guruswami, J. Kleinberg, P. Raghavan and A. Sahai,
in Proceedings of the 32nd Annual ACM Symposium on Theory
of Computing (2000), in special issue of JCSS for STOC 2000.
- Improved
Combinatorial Algorithms for the Facility Location and k-Median
Problems
with S. Guha,
in Proceedings of the 40th Annual IEEE Conference on
Foundations of Computer Science (1999), extended version
- A Constant
Factor Approximation Algorithm for the k-Median Problem
with S. Guha, E. Tardos and D. Shmoys,
in Proceedings of the 31st Annual ACM Symposium on Theory
of Computing (1999),
invited to special issue of JCSS for STOC '99.
- On
Targeting Markov Segments,
with P. Raghavan, S. Rajagopalan, S. Ravikumar, and A. Tomkins,
in Proceedings of the 31st Annual ACM Symposium on Theory
of Computing (1999).
- Approximating
Wire Length in Zero and Bounded Skew Clock Trees
with J. Kleinberg, S. Rajagopalan, S. Ravikumar, A. Sahai and A.
Tomkins,
in Proceedings of the 10th Annual ACM-SIAM Symposium on
Discrete Algorithms (1999), extended version.
- Approximating
a Finite Metric by a Small Number of Tree Metrics,
with C. Chekuri, A. Goel, S. Guha and S. Plotkin,
in Proceedings of the 39th Annual IEEE Conference on
Foundations of Computer Science (1998).
- The
Finite Capacity Dial-A-Ride Problem,
with B. Raghavachari,
in Proceedings of the 39th Annual IEEE Conference on
Foundations of Computer Science (1998)
- Delayed
Information and Action in On-Line Algorithms,
with S. Albers and M. Mitzenmacher,
in Information and Computation, vol 170, pp. 135-152 (2001), preliminary
version in Proceedings of the 39th Annual IEEE Conference on
Foundations of Computer Science (1998).
- A
Derandomization Using Min-Wise Independent Permutations,
with A. Broder and M. Mitzenmacher,
in Proceedings of the 2nd International Workshop on
Randomization and Approximation Techniques in Computer Science (1998).
- Min-Wise
Independent Permutations,
with A. Broder, A. Frieze and M. Mitzenmacher,
in Journal of Computer Systems and Sciences, vol. 60(3), pp. 630-659
(2000) (special issue for STOC '98), preliminary version in
Proceedings of the 30th Annual ACM Symposium on Theory of Computing
(1998),
- Rounding
Via Trees: Deterministic Approximation Algorithms for Group Steiner
Trees and k-Median,
with C. Chekuri, A. Goel and S. Guha,
in Proceedings of the 30th Annual ACM Symposium on Theory
of Computing (1998).
- Algorithms
for Capacitated Vehicle Routing
with S. Khuller and B. Raghavachari,
in Proceedings of the 30th Annual ACM Symposium on Theory
of Computing (1998).
- Approximation
Algorithms for Directed Steiner Tree Problems,
with C. Chekuri, T. Cheung, Z. Dai, A. Goel, S. Guha and M. Li,
in Journal of Algorithms, vol. 33, pp. 73-91 (1999), preliminary
version in Proceedings of the 9th Annual ACM-SIAM Symposium on
Discrete Algorithms (1998).
- The
Dynamic Servers Problem,
with D. Halperin and R. Motwani,
in Proceedings of the 9th Annual ACM-SIAM Symposium on
Discrete Algorithms (1998).
- Incremental Clustering and Dynamic
Information Retrieval,
with C. Chekuri, T. Feder and R. Motwani,
in Proceedings of the 29th Annual ACM Symposium on Theory
of Computing (1997).
- On-line
Load Balancing for Related Machines,
with P. Berman and M. Karpinski,
in Journal of Algorithms, vol. 35(1), pp. 108-121, (2000), preliminary
version in Proceedings of Workshop on Algorithms and Data
Structures (WADS), (1997).
- Constrained
TSP and Low Power Computing,
with C. Silverstein, R. Motwani and P. Raghavan,
in Proceedings of Workshop on Algorithms and Data
Structures (WADS), (1997).
- On Page
Migration and Other Relaxed Task Systems,
with Y. Bartal and P. Indyk,
in Theoretical Computer Science, vol. 268(1), pp. 43-66 (2001),
preliminary version in Proceedings of the 8th Annual ACM-SIAM Symposium
on Discrete Algorithms (1997).
|