Amit Kumar

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

FPT Approximation for Capacitated Sum of Radii.

[BibT_eX]

[DOI]

Jatin Yadav

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

Centralized Selection with Preferences in the Presence of Biases.

[BibT_eX]

[DOI]

Proceedings of the Forty-first International Conference on Machine Learning, 2024

Random Separating Hyperplane Theorem and Learning Polytopes.

[BibT_eX]

[DOI]

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

Universal Weak Coreset.

[BibT_eX]

[DOI]

Proceedings of the Thirty-Eighth AAAI Conference on Artificial Intelligence, 2024

2023

Constant Factor Approximation Algorithm for Weighted Flow-Time on a Single Machine in PseudoPolynomial Time.

[BibT_eX]

[DOI]

Jatin Batra

SIAM J. Comput., December, 2023

Clustering What Matters in Constrained Settings.

[BibT_eX]

[DOI]

CoRR, 2023

Bias in Evaluation Processes: An Optimization-Based Model.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Clustering What Matters in Constrained Settings: Improved Outlier to Outlier-Free Reductions.

[BibT_eX]

[DOI]

Proceedings of the 34th International Symposium on Algorithms and Computation, 2023

Efficient Algorithms and Hardness Results for the Weighted k-Server Problem.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2023

2022

Caching with Time Windows and Delays.

[BibT_eX]

[DOI]

SIAM J. Comput., 2022

Stochastic makespan minimization in structured set systems.

[BibT_eX]

[DOI]

Math. Program., 2022

Online Discrepancy with Recourse for Vectors and Graphs.

[BibT_eX]

[DOI]

Vijaykrishna Gurunathan

Sahil Singla

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

How many Clusters? - An algorithmic answer.

[BibT_eX]

[DOI]

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Online Algorithms with Multiple Predictions.

[BibT_eX]

[DOI]

Proceedings of the International Conference on Machine Learning, 2022

2021

Stochastic Load Balancing on Unrelated Machines.

[BibT_eX]

[DOI]

Math. Oper. Res., 2021

Hardness of Approximation for Orienteering with Multiple Time Windows.

[BibT_eX]

[DOI]

Sanjeev Khanna

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

A Regression Approach to Learning-Augmented Online Algorithms.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Finding k in Latent k- polytope.

[BibT_eX]

[DOI]

Proceedings of the 38th International Conference on Machine Learning, 2021

A Hitting Set Relaxation for $k$-Server and an Extension to Time-Windows.

[BibT_eX]

[DOI]

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

Bag-Of-Tasks Scheduling on Related Machines.

[BibT_eX]

[DOI]

Sahil Singla

Proceedings of the Approximation, 2021

2020

Algorithms for finding k in k-means.

[BibT_eX]

[DOI]

CoRR, 2020

Caching with time windows.

[BibT_eX]

[DOI]

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Multiplicative Rank-1 Approximation using Length-Squared Sampling.

[BibT_eX]

[DOI]

Proceedings of the 3rd Symposium on Simplicity in Algorithms, 2020

FPT Approximation for Constrained Metric k-Median/Means.

[BibT_eX]

[DOI]

Dishant Goyal

Proceedings of the 15th International Symposium on Parameterized and Exact Computation, 2020

Stochastic Makespan Minimization in Structured Set Systems (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2020

Online Carpooling Using Expander Decompositions.

[BibT_eX]

[DOI]

Sahil Singla

Proceedings of the 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2020

On Sampling Based Algorithms for k-Means.

[BibT_eX]

[DOI]

Proceedings of the 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2020

2019

Streaming PTAS for Binary 𝓁0-Low Rank Approximation.

[BibT_eX]

[DOI]

CoRR, 2019

Streaming PTAS for Constrained k-Means.

[BibT_eX]

[DOI]

Dishant Goyal

CoRR, 2019

Battery Scheduling Problem.

[BibT_eX]

[DOI]

Proceedings of the Theory and Applications of Models of Computation, 2019

Elastic Caching.

[BibT_eX]

[DOI]

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Tight FPT Approximations for k-Median and k-Means.

[BibT_eX]

[DOI]

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Non-Clairvoyant Precedence Constrained Scheduling.

[BibT_eX]

[DOI]

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

2018

Faster Algorithms for the Constrained k-means Problem.

[BibT_eX]

[DOI]

Anup Bhattacharya

Theory Comput. Syst., 2018

Rejecting jobs to minimize load and maximum flow-time.

[BibT_eX]

[DOI]

Anamitra Roy Choudhury

Syamantak Das

J. Comput. Syst. Sci., 2018

Sampling in Space Restricted Settings.

[BibT_eX]

[DOI]

Algorithmica, 2018

Approximating Airports and Railways.

[BibT_eX]

[DOI]

Proceedings of the 35th Symposium on Theoretical Aspects of Computer Science, 2018

Approximate Clustering with Same-Cluster Queries.

[BibT_eX]

[DOI]

Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

A Local-Search Algorithm for Steiner Forest.

[BibT_eX]

[DOI]

Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

Non-Preemptive Flow-Time Minimization via Rejections.

[BibT_eX]

[DOI]

Jason Li

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Fully-Dynamic Bin Packing with Little Repacking.

[BibT_eX]

[DOI]

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Constant Factor Approximation Algorithm for Weighted Flow Time on a Single Machine in Pseudo-Polynomial Time.

[BibT_eX]

[DOI]

Jatin Batra

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

2017

Fully-Dynamic Bin Packing with Limited Repacking.

[BibT_eX]

[DOI]

CoRR, 2017

Minimizing Maximum (Weighted) Flow-Time on Related and Unrelated Machines.

[BibT_eX]

[DOI]

Algorithmica, 2017

Online and dynamic algorithms for set cover.

[BibT_eX]

[DOI]

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

The Heterogeneous Capacitated k-Center Problem.

[BibT_eX]

[DOI]

Deeparnab Chakrabarty

Proceedings of the Integer Programming and Combinatorial Optimization, 2017

SpectraMap: Efficiently Constructing a Spatio-temporal RF Spectrum Occupancy Map.

[BibT_eX]

[DOI]

Proceedings of the Communication Systems and Networks - 9th International Conference, 2017

2016

Minimizing average flow-time under knapsack constraint.

[BibT_eX]

[DOI]

Suman Kalyan Bera

Syamantak Das

Theor. Comput. Sci., 2016

The Power of Deferral: Maintaining a Constant-Competitive Steiner Tree Online.

[BibT_eX]

[DOI]

Albert Gu

SIAM J. Comput., 2016

2015

Facility Location with Matroid or Knapsack Constraints.

[BibT_eX]

[DOI]

Math. Oper. Res., 2015

Greedy Algorithms for Steiner Forest.

[BibT_eX]

[DOI]

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

New Approximation Schemes for Unsplittable Flow on a Path.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Minimizing Weighted lp-Norm of Flow-Time in the Rejection Model.

[BibT_eX]

[DOI]

Anamitra Roy Choudhury

Syamantak Das

Proceedings of the 35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science, 2015

2014

Approximation algorithms for the partition vertex cover problem.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2014

A Simple D 2-Sampling Based PTAS for k-Means and Other Clustering Problems.

[BibT_eX]

[DOI]

Algorithmica, 2014

Maintaining Assignments Online: Matching, Scheduling, and Flows.

[BibT_eX]

[DOI]

Cliff Stein

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Online Steiner Tree with Deletions.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

2012

Constant factor approximation algorithm for the knapsack median problem.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Resource augmentation for weighted flow-time explained by dual fitting.

[BibT_eX]

[DOI]

S. Anand

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Efficient on-line algorithm for maintaining k-cover of sparse bit-strings.

[BibT_eX]

[DOI]

Preeti Ranjan Panda

Smruti R. Sarangi

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2012

Approximation Algorithms for the Unsplittable Flow Problem on Paths and Trees.

[BibT_eX]

[DOI]

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2012

2011

Single-path routing for life time maximization in multi-hop wireless networks.

[BibT_eX]

[DOI]

Wirel. Networks, 2011

Approximation Algorithms for Edge Partitioned Vertex Cover Problems

[BibT_eX]

[DOI]

CoRR, 2011

On LP-Based Approximability for Strict CSPs.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

The Matroid Median Problem.

[BibT_eX]

[DOI]

Venkatesan T. Chakaravarthy

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Minimum Cost Resource Allocation for Meeting Job Requirements.

[BibT_eX]

[DOI]

Proceedings of the 25th IEEE International Symposium on Parallel and Distributed Processing, 2011

Contact Center Scheduling with Strict Resource Requirements.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatoral Optimization, 2011

Resource Allocation for Covering Time Varying Demands.

[BibT_eX]

[DOI]

Venkatesan T. Chakaravarthy

Sambuddha Roy

Venkatesan T. Chakaravarthy

Proceedings of the Algorithms - ESA 2011, 2011

Scheduling Resources for Throughput Maximization.

[BibT_eX]

[DOI]

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010

Linear-time approximation schemes for clustering problems in any dimensions.

[BibT_eX]

[DOI]

J. ACM, 2010

Assigning Papers to Referees.

[BibT_eX]

[DOI]

Algorithmica, 2010

Clustering with Spectral Norm and the k-Means Algorithm.

[BibT_eX]

[DOI]

Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

2009

On the Optimality of a Class of LP-based Algorithms.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2009

A constant-factor approximation for stochastic Steiner forest.

[BibT_eX]

[DOI]

Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

A competitive algorithm for minimizing weighted flow time on unrelatedmachines with speed augmentation.

[BibT_eX]

[DOI]

Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

Scheduling with Outliers.

[BibT_eX]

[DOI]

Danny Segev

Proceedings of the Approximation, 2009

2008

Minimizing Total Flow-Time: The Unrelated Case.

[BibT_eX]

[DOI]

V. N. Muralidhara

Proceedings of the Algorithms and Computation, 19th International Symposium, 2008

All-Norms and All-L_p-Norms Approximation Algorithms.

[BibT_eX]

[DOI]

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2008

Efficient Parallel Implementations of Binomial Tree Option Price Valuation.

[BibT_eX]

Mahantesh Halappanavar

Ravi Mukkamala

Mohammad Zubair

Proceedings of the ISCA 21st International Conference on Parallel and Distributed Computing and Communication Systems, 2008

2007

Approximation via cost sharing: Simpler and better approximation algorithms for network design.

[BibT_eX]

[DOI]

J. ACM, 2007

Efficient load-balancing routing for wireless mesh networks.

[BibT_eX]

[DOI]

Yigal Bejerano

Seung-Jae Han

Comput. Networks, 2007

Approximation Algorithms for the Unsplittable Flow Problem.

[BibT_eX]

[DOI]

Algorithmica, 2007

The Priority k-Median Problem.

[BibT_eX]

[DOI]

Proceedings of the FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science, 2007

Order Scheduling Models: Hardness and Algorithms.

[BibT_eX]

[DOI]

Vinayaka Pandit

Proceedings of the FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science, 2007

Minimizing Average Flow-time : Upper and Lower Bounds.

[BibT_eX]

[DOI]

Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 2007

On Configuring BGP Route Reflectors.

[BibT_eX]

[DOI]

Proceedings of the Second International Conference on COMmunication System softWAre and MiddlewaRE (COMSWARE 2007), 2007

Stochastic Steiner Tree with Non-uniform Inflation.

[BibT_eX]

[DOI]

MohammadTaghi Hajiaghayi

Proceedings of the Approximation, 2007

2006

Fairness Measures for Resource Allocation.

[BibT_eX]

[DOI]

Jon M. Kleinberg

SIAM J. Comput., 2006

Minimizing average flow time on related machines.

[BibT_eX]

[DOI]

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Better Algorithms for Minimizing Average Flow-Time on Related Machines.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

Enhanced distributed hash tables for complex queries.

[BibT_eX]

[DOI]

Pankaj Garg

Huzur Saran

Proceedings of the First International Conference on COMmunication System softWAre and MiddlewaRE (COMSWARE 2006), 2006

2005

Wavelet synopses for general error metrics.

[BibT_eX]

[DOI]

ACM Trans. Database Syst., 2005

XML stream processing using tree-edit distance embeddings.

[BibT_eX]

[DOI]

ACM Trans. Database Syst., 2005

On a bidirected relaxation for the MULTIWAY CUT problem.

[BibT_eX]

[DOI]

Chandra Chekuri

Discret. Appl. Math., 2005

Building Edge-Failure Resilient Networks.

[BibT_eX]

[DOI]

Algorithmica, 2005

Join-distinct aggregate estimation over update streams.

[BibT_eX]

[DOI]

Proceedings of the Twenty-fourth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2005

Linear Time Algorithms for Clustering Problems in Any Dimensions.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 32nd International Colloquium, 2005

Where's the Winner? Max-Finding and Sorting with Metric Costs.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2005

2004

Traveling with a Pez Dispenser (or, Routing Issues in MPLS).

[BibT_eX]

[DOI]

Rajeev Rastogi

SIAM J. Comput., 2004

Primal-Dual Algorithms for Connected Facility Location Problems.

[BibT_eX]

[DOI]

Chaitanya Swamy

Algorithmica, 2004

Multi-processor scheduling to minimize flow time with epsilon resource augmentation.

[BibT_eX]

[DOI]

Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

Deterministic Wavelet Thresholding for Maximum-Error Metrics.

[BibT_eX]

[DOI]

Proceedings of the Twenty-third ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2004

A Simple Linear Time (1+έ)-Approximation Algorithm for k-Means Clustering in Any Dimensions.

[BibT_eX]

[DOI]

Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

Maximum Coverage Problem with Group Budget Constraints and Applications.

[BibT_eX]

[DOI]

Chandra Chekuri

Proceedings of the Approximation, 2004

2003

Optimal configuration of OSPF aggregates.

[BibT_eX]

[DOI]

IEEE/ACM Trans. Netw., 2003

Simpler and better approximation algorithms for network design.

[BibT_eX]

[DOI]

Tim Roughgarden

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Tree based MPLS routing.

[BibT_eX]

[DOI]

Mikkel Thorup

Proceedings of the SPAA 2003: Proceedings of the Fifteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2003

Correlating XML data streams using tree-edit distance embeddings.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Second ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2003

Exploring the trade-off between label size and stack depth in MPLS Routing.

[BibT_eX]

[DOI]

Rajeev Rastogi

Proceedings of the Proceedings IEEE INFOCOM 2003, The 22nd Annual Joint Conference of the IEEE Computer and Communications Societies, San Franciso, CA, USA, March 30, 2003

Approximation Via Cost-Sharing: A Simple Approximation Algorithm for the Multicommodity Rent-or-Buy Problem.

[BibT_eX]

[DOI]

Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

2002

Algorithms for Network Management.

[BibT_eX]