Amit Kumar's Homepage (original) (raw)

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

Research

My research lies in the areas of combinatorial optimization and online algorithms. My recent work has focussed on

• Clustering problems with side constraints or data-dependent attributes.
• Understanding biases in evaluation processes.
• Online allocation and server problems with additional constraints.

Publications (google scholar)

2025

• Tight Results for Online Convex Paging
  (with Anupam Gupta and Debmalya Panigrahi)
  To appear in ACM Symposium on Theory of Computing (STOC), 2025
• Breaking the Two Approximation Barrier for Various Consensus Clustering Problems
  (with Debarati Das)
  ACM-SIAM Symposium on Discrete Algorithms (SODA), 2025.

2024

• Centralized Selection with Preferences in the Presence of Biases
  (with L. Elisa Celis, Nisheeth K. Vishnoi and Andrew Xu)
  International Conference on Machine Learning (ICML), 2024.
• Random Separating Hyperplane Theorem and Learning Polytopes
  (with Chiranjib Bhattacharyya and Ravi Kannan)
  International Colloquium on Automata, Languages and Programming (ICALP), 2024.
• Fully-Dynamic Load Balancing
  (with Ayoub Foussoul and Vineet Goyal)
  Integer Programming and Combinatorial Optimization (IPCO), 2024
• Towards Fairness in Online Service with k Servers and its Application on Fair Food Delivery
  (with Daman Deep Singh and Abhijnan Chakraborty)
  AAAI Conference on Artificial Intelligence (AAAI), 2024
• Universal Weak Coreset
  (with Ragesh Jaiswal)
  AAAI Conference on Artificial Intelligence (AAAI), 2024
• FPT Approximation for Capacitated Sum of Radii
  (with Ragesh Jaiswal and Jatin Yadav)
  Innovations in Theoretical Computer Science (ITCS), 2024
• Poly-logarithmic Competitiveness for the k-taxi problem
  (with Anupam Gupta and Debmalya Panigrahi)
  ACM-SIAM Symposium on Discrete Algorithms (SODA), 2024.

2023

• Bias in Evaluation Processes: An Optimization-Based Model
  (with Elisa Celis, Anay Mehrotra and Nisheeth Vishnoi)
  Neural Information Processing Systems (NeurIPS), 2023
• Clustering What Matters in Constrained Settings
  (with Ragesh Jaiswal)
  (Best paper award)
  International Symposium on Algorithms and Computation (ISAAC), 2023
• Efficient Algorithms and Hardness Results for the Weighted k-server Problem
  (with Anupam Gupta and Debmalya Panigrahi)
  Approximation Algorithms for Combinatorial Optimization Problems(APPROX), 2023.

2022

• Online Algorithms with Multiple Predictions
  (with Keerti Anand, Rong Ge and Debmalya Panigrahi)
  International Conference on Machine Learning (ICML), 2022
• How many Clusters? - An algorithmic answer
  (with Chiranjib Bhattacharyya and Ravi Kannan)
  ACM-SIAM Symposium on Discrete Algorithms (SODA), 2022.
• Online Discrepancy with Recourse for Vectors and Graphs
  (with Anupam Gupta, Vijaykrishna Gurunathan, Ravishankar Krishnaswamy and Sahil Singla)
  ACM-SIAM Symposium on Discrete Algorithms (SODA), 2022.

2021

• A Regression Approach to Learning-Augmented Online Algorithms
  (with Keerti Anand, Rong Ge and Debmalya Panigrahi)
  Neural Information Processing Systems (NeurIPS), 2021
• A Hitting Set Relaxation for k-Server and an Extension to Time-Windows
  (with Anupam Gupta and Debmalya Panigrahi)
  IEEE Symposium on Foundations of Computer Science (FOCS), 2021
• Bag-of-Tasks Scheduling on Related Machines
  (with Anupam Gupta and Sahil Singla)
  Approximation Algorithms for Combinatorial Optimization Problems(APPROX), 2021.
• Finding k in Latent k-polytope
  (with Chiranjib Bhattacharyya and Ravi Kannan)
  International Conference on Machine Learning (ICML), 2021.
• Hardness of Approximation for Orienteering with Multiple Time Windows
  (with Naveen Garg and Sanjeev Khanna)
  ACM-SIAM Symposium on Discrete Algorithms (SODA), 2021.

2020

• On Sampling Based Algorithms for k-means
  (with Anup Bhattacharya, Dishant Goyal and Ragesh Jaiswal)
  Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2020.
• Online Carpooling using Expander Decompositions
  (with Anupam Gupta, Sahil Singla and Ravishankar Krishnaswamy)
  Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2020.
• FPT Approximation for Constrained Metric k-Median/Means
  (with Dishant Goyal and Ragesh Jaiswal)
  International Symposium on Parameterized and Exact Computation (IPEC), 2020
• Caching with Time Windows
  (with Anupam Gupta, Debmalya Panigrahi)
  ACM Symposium on Theory of Computing (STOC), 2020
• Stochastic Makespan Minimization in Structured Set Systems
  (with Anupam Gupta, Viswanath Nagarajan and Xiangkun Shen)
  Integer Programming and Combinatorial Optimization (IPCO), 2020
• Multiplicative Rank-1 Approximation using Length-Squared Sampling
  (with Ragesh Jaiswal)
  Symposium on Simplicity in Algorithms (SOSA), 2020

2019

• Non-clairvoyant Precedence Constrained Scheduling
  (with Naveen Garg, Anupam Gupta and Sahil Singla)
  International Colloquium on Automata, Languages and Programming (ICALP), 2019.
• Tight FPT Approximations for k-Median and k-Means
  (with Vincent Cohen-Addad, Anupam Gupta, Euiwoong Lee and Jason Li)
  International Colloquium on Automata, Languages and Programming (ICALP), 2019.
• Elastic Caching
  (with Anupam Gupta, Ravishakar Krishnaswamy and Debmalya Panigrahi )
  ACM-SIAM Symposium on Discrete Algorithms (SODA), 2019.

2018

• Constant Factor Approximation Algorithm for Weighted Flow Time on a Single Machine in Pseudo-polynomial time
  (with Jatin Batra and Naveen Garg).
  IEEE Symposium on Foundations of Computer Sciene (FOCS), 2018.
• Fully-Dynamic Bin Packing with Limited Repacking
  (with Björn Feldkord, Matthias Feldotto, Anupam Gupta, Guru Guruganesh, Sören Riechers and David Wajc)
  International Colloquium on Automata, Languages and Programming (ICALP), 2018.
• Non-Preemptive Flow-Time Minimization via Rejections
  (with Anupam Gupta and Jason Li)
  International Colloquium on Automata, Languages and Programming (ICALP), 2018.
• Approximate Clustering with Same Cluster Queries
  (with Nir Ailon, Anup Bhattacharya and Ragesh Jaiswal)
  Innovations in Theoretical Computer Science (ITCS), 2018
• A Local Search Algorithm for Steiner Forest
  (with Martin Gross, Anupam Gupta, Jannik Matuschke, Daniel Schmidt, Melanie Schmidt and Jose Verschae)
  Innovations in Theoretical Computer Science (ITCS), 2018.
• Stochastic Load Balancing on Unrelated Machines
  (with Anupam Gupta, Viswanath Nagarajan and Xiangkun Shen)
  ACM-SIAM Symposium on Discrete Algorithms (SODA), 2018.
• Approximating Airports and Railways
  (with Anna Adamaszek, Antonios Antoniadis and Tobias Mömke)
  Symposium on Theoretical Aspects of Computer Science (STACS), 2018.

2017

• Online and Dynamic Algorithms for Set Cover
  (with Anupam Gupta, Ravishankar Krishnaswamy and Debmalya Panigrahi)
  ACM Symposium on Theory of Computing (STOC), 2017
• The Heterogeneous Capacitated k-Center Problem
  (with Deeparnab Chakrabarty and Ravishankar Krishnaswamy)
  Integer Programming and Combinatorial Optimization (IPCO), 2017.

2016

• Faster Algorithms for the Constrained k-Means Problem
  (with Anup Bhattacharya and Ragesh Jaiswal)
  Symposium on Theoretical Aspects of Computer Science (STACS), 2016

2015

• Greedy Algorithms for Steiner Forest
  (with Anupam Gupta)
  ACM Symposium on Theory of Computing (STOC), 2015
• New Approximation Schemes for Unsplittable Flow on a Path
  (with Jatin Batra, Naveen Garg, Tobias Momke and Andreas Weise)
  ACM-SIAM Symposium on Discrete Algorithms (SODA), 2015
• Rejecting Jobs to Minimize Load and Maximum Flow-time
  (with Anamitra Choudhury, Syamantak Das and Naveen Garg)
  ACM-SIAM Symposium on Discrete Algorithms (SODA), 2015
• Sampling in Space Restricted Settings
  (with Anup Bhattacharya, Davis Issac and Ragesh Jaiswal)
  International Computing and Combinatorics Conference (COCOON), 2015
• Minimizing Weighted lp-Norm of Flow-Time in the Rejection Model
  (with Anamitra Roy Choudhury and Syamantak Das)
  FSTTCS 2015

2014

• Maintaining Assignments Online: Matching, Scheduling and Flows
  (with Anupam Gupta and Cliff Stein)
  ACM-SIAM Symposium on Discrete Algorithms (SODA), 2014
• Online Steiner Tree with Deletions
  (with Anupam Gupta)
  ACM-SIAM Symposium on Discrete Algorithms (SODA), 2014
• Minimizing Average Flow-Time under Knapsack Constraint
  (with Suman Kalyan Bera and Syamantak Das)
  International Computing and Combinatorics Conference (COCOON), 2014

2013

• Minimizing maximum (weighted) flow-time on related and unrelated machines
  (with S. Anand, Karl Bringmann, Tobias Friedrich and Naveen Garg)
  International Colloquium on Automata, Languages and Programming (ICALP), 2013
• The Power of Deferral: Maintaining a Constant-Competitive Steiner Tree Online
  (with Albert Gu and Anupam Gupta)
  ACM Symposium on Theory of Computing (STOC), 2013

2012

• A Simple D^2-sampling based PTAS for k-means and other Clustering Problems
  (with Ragesh Jaiswal and Sandeep Sen)
  International Computing and Combinatorics Conference (COCOON), 2012
• 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
  ACM-SIAM Symposium on Discrete Algorithms (SODA), 2012
• Resource Augmentation for Weighted Flow-time explained by Dual Fitting
  (with S. Anand and Naveen Garg)
  ACM-SIAM Symposium on Discrete Algorithms (SODA), 2012

2011

• Resource Allocation for Covering Time Varying Demands.
  (with Venkatesan Chakaravarthy, Sambuddha Roy and Yogish Sabharwal)
  European Symposium on Algorithms (ESA), 2011
• Scheduling Resources for Throughput Maximization
  (with Venkatesan Chakaravarthy, Vinayaka Pandit, Sambuddha Roy and Yogish Sabharwal)
  International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2011.
• Contact Center Scheduling with Strict Resource Requirements
  (with Aman Dhesi, Pranav Gupta, Gyana Parija and Sambuddha Roy)
  Integer Programming and Combinatorial Optimization (IPCO), 2011
• The Matroid Median Problem
  (with R. Krishnaswamy, V. Nagarajan, B. Saha and Y. Sabharwal)
  ACM-SIAM Symposium on Discrete Algorithms (SODA), 2011
• On LP-based Approximability for Strict CSPs
  (with Rajsekar Manokaran, Madhur Tulsiani and Nisheeth Vishnoi)
  ACM-SIAM Symposium on Discrete Algorithms (SODA), 2011

2010

• Clustering with Spectral Norm and the k-means Algorithm
  (with Ravi Kannan)
  IEEE Symposium on Foundations of Computer Science (FOCS), 2010.
• Assigning Papers to Referees
  (with Naveen Garg, T. Kavitha, Kurt Mehlhorn and Julian Mestre)
  Algorithmica, 2010.

2009

• Scheduling with Outliers
  (with Anupam Gupta, Ravishankar Krishnaswamy and Danny Segev)
  International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2009.
• A constant factor approximation for Stochastic Steiner Forest
  (with Anupam Gupta)
  ACM Symposium on Theory of Computing (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)
  ACM Symposium on Theory of Computing (STOC), 2009

2008

• Minimizing total flow-time : the unrelated case
  (with Naveen Garg)
  ISAAC, 2008.
• All norms and all L-p norms Approximation algorithms
  (with D. Golovin, A. Gupta and K. Tangwongsan)
  FSTTCS 2008

2007

• 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)
  IEEE Symposium on Foundations of Computer Science (FOCS), 2007.
• Stochastic Steiner Tree with Non-Uniform Inflation
  (with Anupam Gupta and MohammadTaghi Hajiaghayi)
  International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2007.
• On Configuring BGP Route Reflectors
  (with Yuri Breitbart, Minos Garofalakis and Rajeev Rastogi)
  COMSWARE 2007

2006

• Better algorithms for minimizing average flow-time on related machines.
  (with Naveen Garg)
  International Colloquium on Automata, Languages and Programming (ICALP), 2006
• Minimizing average flow-time on related machines
  (with Naveen Garg)
  ACM Symposium on Theory of Computing (STOC), 2006

2005

• Linear Time Algorithms for Clustering Problems in any dimensions
  (with Sandeep Sen and Yogish Sabharwal)
  International Colloquium on Automata, Languages and Programming (ICALP), 2005
• Where's the Winner ? (Max-finding and Sorting with Metric Comparision Costs)
  (with A. Gupta)
  International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (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
• Join-Distinct Aggregate Estimation over Update Streams
  (with Sumit Ganguly, M. Garofalakis and Rajeev Rastogi)
  ACM PODS, 2005

2004

• A simple linear time (1+epsilon)-approximation algorithm for k-means clustering in any dimensions.
  (with Sandeep Sen and Yogish Sabharwal)
  IEEE Symposium on Foundations of Computer Science (FOCS), 2004.
• Maximum Coverage Problem with Group Budget Constraints.
  (with C. Chekuri)
  International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (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 (STOC), 2004.
• Deterministic Wavelet Thresholding for Maximum-Error Metrics.
  (with M. Garofalakis)
  ACM PODS, 2004

2003

• Approximation via Cost-Sharing : A Simple Approximation Algorithm for the Multi-commodity Rent-or-Buy Problem.
  (with A. Gupta, M. Pal, T. Roughgarden)
  IEEE Symposium on Foundations of Computer Science (FOCS), 2003.
• Simpler and better algorithms for network design.
  (with A. Gupta, T. Roughgarden)
  ACM Symposium on Theory of Computing (STOC), 2003.
• Exploring the trade-off between label size and stack depth in MPLS Routing.
  (with A. Gupta, R. Rastogi)
  IEEE INFOCOM, 2003
• Correlating XML Data Streams Using Tree-Edit Distance Embeddings.
  (with M. Garofalakis)
  ACM PODS, 2003

2002

• A Constant Factor Approximation Algorithm for the Multicommodity Rent-or-Buy Problem.
  (with A. Gupta, T. Roughgarden)
  IEEE Symposium on Foundations of Computer Science (FOCS), 2002.
• Primal-dual Algorithms for Connected Facility Location Problems.
  (with C. Swamy)
  International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2002.
• Approximation Algorithms for the Unsplittable Flow Problem.
  (with A. Chakrabarti, C. Chekuri, A. Gupta)
  International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2002.
• Building edge-failure resilient networks.
  (with C. Chekuri, A. Gupta, S. Naor, D. Raz)
  Integer Programming and Combinatorial Optimization (IPCO), 2002.
• Optimal configuration of OSPF aggregates.
  (with Y. Breitbart, M. Garofalakis, R. Rastogi)
  IEEE INFOCOM, 2002.

2001

• Traveling with a Pez Dispenser (Or, Routing Issues in MPLS).
  (with Anupam Gupta, and Rajeev Rastogi)
  IEEE Symposium on Foundations of Computer Science (FOCS), 2001.
• Sorting and Selection with Structured Costs.
  (with Anupam Gupta)
  IEEE Symposium on Foundations of Computer Science (FOCS), 2001.
• Algorithms for provisioning virtual private networks in the hose model.
  (with Rajeev Rastogi, Abraham Silberschatz, Bulent Yener)
  ACM SIGCOMM
• Provisioning a virtual private network: a network design problem for multicommodity flow.
  (with Anupam Gupta, Jon Kleinberg, Rajeev Rastogi, Bulent Yener)
  ACM Symposium on Theory of Computing (STOC), 2001.

2000

• Fairness Measures for Resource Allocation.
  (with Jon Kleinberg)
  IEEE Symposium on Foundations of Computer Science (FOCS), 2000.
• Connectivity and inference problems for temporal networks.
  (with David Kempe and Jon Kleinberg)
  ACM Symposium on Theory of Computing (STOC), 2001.

1999

• Wavelength Conversion in Optical Networks.
  (with Jon Kleinberg)
  ACM-SIAM Symposium on Discrete Algorithms (SODA), 1999

Contact Information

Email: amitk at cse.iitd.ernet.in
Phone: +91-11-26591286
Office Address: Room 417, Bharti Building, IIT Delhi