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.