Amit Kumar's homepage

Amit Kumar

Professor
Department of Computer Science and Engineering
Indian Institute of Technology
Hauz Khas, New Delhi - 110016

Teaching

Data Structures

Publications

Clustering

A Simple D^2-sampling based PTAS for k-means and other Clustering Problems
(with Ragesh Jaiswal and Sandeep Sen)
COCOON, 2012
Clustering with Spectral Norm and the k-means Algorithm
(with Ravi Kannan)
FOCS, 2010
Linear Time Algorithms for Clustering Problems in any dimensions
(with Sandeep Sen and Yogish Sabharwal)
ICALP, 2005.
A simple linear time (1+epsilon)-approximation algorithm
for k-means clustering in any dimensions.
(with Sandeep Sen and Yogish Sabharwal)
IEEE Foundations of Computer Science, 2004.

Approximation Algorithms

Minimizing maximum (weighted) flow-time on related and unrelated machines
(with S. Anand, Karl Bringmann, Tobias Friedrich and Naveen Garg)
To appear in ICALP 2013
The Power of Deferral: Maintaining a Constant-Competitive Steiner Tree Online
(with Albert Gu and Anupam Gupta)
To appear in STOC 2013
Approximation Algorithms for the Unsplittable Flow Problem on Paths and Trees
(with Khaled Elbassio, Naveen Garg, Divya Gupta, Vishal Narula and Arindam Pal)
FSTTCS 2012
Efficient on-line algorithms for maintaining k-cover of sparse bit-strings
(with Preeti Panda and Smruti Sarangi)
FSTTCS 2012
Constant factor approximation algorithm for the knapsack median problem
SODA 2012
Resource Augmentation for Weighted Flow-time explained by Dual Fitting
(with S. Anand and Naveen Garg)
SODA 2012
Resource Allocation for Covering Time Varying Demands.
(with Venkatesan Chakaravarthy, Sambuddha Roy and Yogish Sabharwal)
ESA 2011
Scheduling Resources for Throughput Maximization
(with Venkatesan Chakaravarthy, Vinayaka Pandit, Sambuddha Roy and Yogish Sabharwal)
APPROX 2011
Contact Center Scheduling with Strict Resource Requirements
(with Aman Dhesi, Pranav Gupta, Gyana Parija and Sambuddha Roy)
IPCO 2011
The Matroid Median Problem
(with R. Krishnaswamy, V. Nagarajan, B. Saha and Y. Sabharwal)
SODA 2011
On LP-based Approximability for Strict CSPs
(with Rajsekar Manokaran, Madhur Tulsiani and Nisheeth Vishnoi)
SODA 2011
Assigning Papers to Referees
(with Naveen Garg, T. Kavitha, Kurt Mehlhorn and Julian Mestre)
Algorithmica, 2010.
Scheduling with Outliers
(with Anupam Gupta, Ravishankar Krishnaswamy and Danny Segev)
APPROX, 2009
A constant factor approximation for Stochastic Steiner Forest
(with Anupam Gupta)
STOC, 2009
A competitive algorithm for minimizing weighted flow time on unrelated machines with speed augmentation
(with Jivitej Chadha, Naveen Garg and V.N. Muralidhara)
STOC, 2009
Minimizing total flow-time : the unrelated case
(with Naveen Garg)
ISAAC, 2008.
Order Scheduling Models : Hardness and Algorithms
(with Naveen Garg and Vinayaka Pandit)
FSTTCS, 2007.
The priority k-median problem
(with Yogish Sabharwal)
FSTTCS, 2007.
Minimizing average flowtime : Upper and Lower Bounds
(with Naveen Garg)
FOCS, 2007.
Stochastic Steiner Tree with Non-Uniform Inflation
(with Anupam Gupta and MohammadTaghi Hajiaghayi)
APPROX, 2007
Better algorithms for minimizing average flow-time on related machines.
(with Naveen Garg)
ICALP, 2006.
Minimizing average flow-time on related machines
(with Naveen Garg )
ACM Symposium on Theory of Computing, 2006
Where's the Winner ? (Max-finding and Sorting with Metric Comparision Costs)
(with A. Gupta )
APPROX 2005.
On a bidirected relaxation for the multiway cut problem
(with Chandra Chekuri and Anupam Gupta)
Discrete Applied Mathematics 150(1-3):67-79
Maximum Coverage Problem with Group Budget Constraints.
(with C. Chekuri )
APPROX 2004.
Multi-processor Scheduling for Minimizing Flow Time with
epsilon-Resource Augmentation.
(with A. Goel , C. Chekuri , S. Khanna )
ACM Symposium on Theory of Computing, 2004.
Approximation via Cost-Sharing : A Simple Approximation
Algorithm for the Multi-commodity Rent-or-Buy Problem.
(with A. Gupta , M. Pal , T. Roughgarden )
IEEE Foundations of Computer Science, 2003.
Simpler and better algorithms for network design.
(with A. Gupta , T. Roughgarden )
ACM Symposium on Theory of Computing, 2003.
A Constant Factor Approximation Algorithm for the
Multicommodity Rent-or-Buy Problem.
(with A. Gupta , T. Roughgarden )
IEEE Foundations of Computer Science, 2002.
Primal-dual Algorithms for Connected Facility Location Problems.
(with C. Swamy )
APPROX 2002.
Approximation Algorithms for the Unsplittable Flow Problem.
(with A. Chakrabarti , C. Chekuri , A. Gupta )
APPROX 2002.

Network Management and Routing

On Configuring BGP Route Reflectors
(with Yuri Breitbart, Minos Garofalakis and Rajeev Rastogi)
COMSWARE 2007
Exploring the trade-off between label size and stack depth in MPLS Routing.
(with A. Gupta and R. Rastogi )
IEEE INFOCOM, 2003
Building edge-failure resilient networks.
(with C. Chekuri , A. Gupta , S. Naor , D. Raz )
IPCO 2002.
Optimal configuration of OSPF aggregates.
(with Y. Breitbart , M. Garofalakis , R. Rastogi )
IEEE INFOCOM, 2002.
Routing Issues in MPLS (Or, How to Travel with a Pez Dispenser).
(with A. Gupta , R. Rastogi )
IEEE Symposium on Foundations of Computer Science, 2001.
Algorithms for provisioning VPNs in the hose model .
(with R. Rastogi , A. Silberschatz , B. Yener )
ACM SIGCOMM, 2001.
Provisioning a virtual private network : A network design problem for multicommodity flow.
(with A. Gupta , J. Kleinberg , R. Rastogi , B. Yener )
ACM Symposium on Thoery of Computing, 2001.
Wavelength Conversion in optical networks.
(with J. Kleinberg )
ACM-SIAM Symposium on Discrete Algorithms, 1999.

Databases

Join-Distinct Aggregate Estimation over Update Streams
(with Sumit Ganguly, M. Garofalakis and Rajeev Rastogi)
ACM PODS, 2005
Deterministic Wavelet Thresholding for Maximum-Error Metrics.
(with M. Garofalakis )
ACM PODS, 2004
Correlating XML Data Streams Using Tree-Edit Distance Embeddings.
(with M. Garofalakis )
ACM PODS, 2003

Fairness

All norms and all L-p norms Approximation algorithms
(with D. Golovin, A. Gupta and K. Tangwongsan)
FSTTCS 2008
Fairness measures for resource allocation.
(with J. Kleinberg )
IEEE Symposium on Foundations of Computer Science, 2000.

Miscellaneous

Sorting and Selection with Structured Costs.
(with A. Gupta )
IEEE Symposium on Foundations of Computer Science, 2001.
Connectivity and inference problems for temporal networks.
(with D. Kempe , J. Kleinberg )
ACM Symposium on Thoery of Computing, 2000.

Contact Information :
email : amitk at cse.iitd.ernet.in
Phone : +91-11-26591286

Biographical Sketch

Links :