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.
  

Teaching

Courses Taught:

• Introduction to Automata and Theory of Computation (COL 352)
• Advanced Data Structures and Algorithms (COL 702)
• Data Structures (COL 106)
• Numerical analysis and scientific computing (COL 726)
• Design and Analysis of Algorithms (COL 351)
• Mathematical Programming (COL 756)
• Discrete Mathematics (COL 202)
• Advanced Algorithms (COL 758)
• Approximation Algorithms (COL 754)

Publications (google scholar)

2024

• Centralized Selection with Preferences in the Presence of Biases
  (with L. Elisa Celis, Nisheeth K. Vishnoi and Andrew Xu)
  To appear in 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)
  To appear in 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.
  
  

Contact Information

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