This page is archived
Selected Publications
- A Constant-Factor Approximation for Multi-Covering with Disks , in SoCG 13. This
follow-up note gives a different insight on the algorithm in the paper,
and also resolves the first open question posed there.
- Weighted Geometric Set Cover
via Quasi-Uniform Sampling , in STOC 10.
- Sampling Based Dimension Reduction
for Subspace Approximation , with Amit Deshpande, in STOC 07. This is
a fuller version which, though poorly formatted, contains
the proof for the dimension reduction result for projective clustering.
- Efficient Subspace Approximation
Algorithms , with N. D. Shyamalkumar, in SODA 07.
- Leontief Economies Encode
Non-Zero Sum Two Player Games , with Bruno Codenotti, Amin Saberi,
and Yinyu Ye, in SODA 06.
- Equilibria for Economies with
Production: Constant-Returns technologies and Production Planning
Constraints, with Kamal Jain, in SODA 06.
- No Coreset, No Cry: 2, with
Mike Edwards, in FSTTCS 05.
- Market Equilibrium for CES Exchange
Economies: Existence, Multiplicity, and Computation , with
Bruno Codenotti, Ben McCune, and Sriram Penumatcha, in FSTTCS 05.
- Market Equilibrium via the
Excess Demand Function , with Bruno Codenotti and
Benton McCune, in STOC 05
- A Near-Linear Constant-Factor
Approximation for Euclidean Bipartite Matching ? , with Pankaj
Agarwal, in SoCG 04
- Graph Decomposition and the Greedy algorithm
for Edge-disjoint Paths, with Ganesh Venkataraman, in SODA 04
- Buffer Minimization via Max-coloring,
with Sriram Pemmaraju and Raviv Raman, in SODA 04
- High-Dimensional Shape Fitting in
Near-Linear time, with Sariel Har-Peled, in SoCG 2003
- Approximating the Radii of Point Sets, with S. Venkatesh and Jiawei Zhang, in FOCS 2002
- Approximation Algorithms for k-line center, with
Pankaj Agarwal and Cecilia Procopiuc, in ESA 2002
- Projective Clustering in high dimensions using core sets , with Sariel Har-Peled, in SoCG 2002
- Approximate Shape fitting via Linearization ,
full version that combines a FOCS 2001 paper of Har-Peled and myself with
a SODA 2001 paper of Agarwal and Har-Peled
- A divide-and-conquer algorithm for mincost
perfect matching in the plane , in FOCS 1998. Here is an
older but more complete version that in particular describes how the
semi-separated decomposition is computed.