Jaswinder and Tarwinder Chadha Chair Professor
Department of Computer Science and Engineering
Indian Institute of Technology
Hauz Khas, New Delhi - 110016
How many Clusters? - An algorithmic answer
(with Chiranjib Bhattacharyya and Ravi Kannan) To appear in 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) To appear in 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) To appear in 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) To appear in 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.
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
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
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.
Scheduling with Outliers
(with Anupam Gupta, Ravishankar Krishnaswamy and Danny Segev) International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2009.
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
Maximum Coverage Problem with Group Budget Constraints.
(with C. Chekuri) International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2004.