ravi2024.bib

@article{doi:10.1137/20M1360645,
author = {Krishnaswamy, Ravishankar and Nagarajan, Viswanath and Pruhs, Kirk and Stein, Clifford},
title = {Cluster Before You Hallucinate: Node-Capacitated Network Design and Energy Efficient Routing},
journal = {SIAM Journal on Computing},
volume = {53},
number = {3},
pages = {588-623},
year = {2024},
doi = {10.1137/20M1360645},
URL = { https://doi.org/10.1137/20M1360645}
}


@inproceedings{multifilter-anns,
  author       = {Siddharth Gollapudi and Sandeep Silwal and Varun Suriyanarayana and Sepideh Mahabadi and Phil Bernstein and Jakub Tarnawski and Suryansh Gupta and Gopal Srinivasa and Ravishankar Krishnaswamy},
  title        = {Graph-Based Algorithms for Approximate Nearest Neighbor Search with Multiple Filters},
  booktitle    = {submitted to NeurIPS 2024},
  year         = {2024},
}

@inproceedings{ood-diskann,
  author       = {Shikhar Jaiswal and Ankit Garg and Harsha Vardhan Simhadri and Ravishankar Krishnaswamy},
  title        = {OOD-DiskANN: Adapting nearest neighbor search to far away queries},
  booktitle    = {submitted to NeurIPS 2024},
  year         = {2024},
}

@inproceedings{DBLP:conf/innovations/0004KSS23,
  author       = {Varun Gupta and
                  Ravishankar Krishnaswamy and
                  Sai Sandeep and
                  Janani Sundaresan},
  title        = {Look Before, Before You Leap: Online Vector Load Balancing with Few
                  Reassignments},
  booktitle    = {14th Innovations in Theoretical Computer Science Conference, {ITCS}
                  2023, January 10-13, 2023, MIT, Cambridge, Massachusetts, {USA}},
  series       = {LIPIcs},
  volume       = {251},
  pages        = {65:1--65:17},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
  year         = {2023},
}

@inproceedings{DBLP:conf/stoc/Krishnaswamy0S23,
  author       = {Ravishankar Krishnaswamy and
                  Shi Li and
                  Varun Suriyanarayana},
  title        = {Online Unrelated-Machine Load Balancing and Generalized Flow with
                  Recourse},
  booktitle    = {Proceedings of the 55th Annual {ACM} Symposium on Theory of Computing,
                  {STOC} 2023, Orlando, FL, USA, June 20-23, 2023},
  pages        = {775--788},
  publisher    = {{ACM}},
  year         = {2023},
}

@inproceedings{DBLP:conf/www/GollapudiKSKBRL23,
  author       = {Siddharth Gollapudi and
                  Neel Karia and
                  Varun Sivashankar and
                  Ravishankar Krishnaswamy and
                  Nikit Begwani and
                  Swapnil Raz and
                  Yiyong Lin and
                  Yin Zhang and
                  Neelam Mahapatro and
                  Premkumar Srinivasan and
                  Amit Singh and
                  Harsha Vardhan Simhadri},
  title        = {Filtered-DiskANN: Graph Algorithms for Approximate Nearest Neighbor
                  Search with Filters},
  booktitle    = {Proceedings of the {ACM} Web Conference 2023, {WWW} 2023, Austin,
                  TX, USA, 30 April 2023 - 4 May 2023},
  pages        = {3406--3416},
  publisher    = {{ACM}},
  year         = {2023},
}



@inproceedings{DBLP:conf/soda/GuptaGKKS22,
  author    = {Anupam Gupta and
               Vijaykrishna Gurunathan and
               Ravishankar Krishnaswamy and
               Amit Kumar and
               Sahil Singla},
  title     = {Online Discrepancy with Recourse for Vectors and Graphs},
  booktitle = {Proceedings of the 2022 {ACM-SIAM} Symposium on Discrete Algorithms,
               {SODA} 2022},
  pages     = {1356--1383},
  publisher = {{SIAM}},
  year      = {2022},
}

@inproceedings{DBLP:conf/nips/SimhadriWADBBCH21,
  author    = {Harsha Vardhan Simhadri and
               George Williams and
               Martin Aum{\"{u}}ller and
               Matthijs Douze and
               Artem Babenko and
               Dmitry Baranchuk and
               Qi Chen and
               Lucas Hosseini and
               Ravishankar Krishnaswamy and
               Gopal Srinivasa and
               Suhas Jayaram Subramanya and
               Jingdong Wang},
  title     = {NeurIPS'21 Challenge on Billion-Scale Approximate Nearest
               Neighbor Search},
  series    = {Proceedings of Machine Learning Research},
  volume    = {176},
  pages     = {177--189},
  publisher = {{PMLR}},
  year      = {2021},
}



@inproceedings{GuptaKS20,
	author    = {Varun Gupta and
	Ravishankar Krishnaswamy and
	Sai Sandeep},
	title     = {Permutation Strikes Back: The Power of Recourse in Online Metric Matching},
	booktitle = {34th Annual Workshop on Approximation Algorithms APPROX},
	year      = {2020}
}


@article{AntoniadisIKMNP20,
	author    = {Antonios Antoniadis and
	Sungjin Im and
	Ravishankar Krishnaswamy and
	Benjamin Moseley and
	Viswanath Nagarajan and
	Kirk Pruhs and
	Clifford Stein},
	title     = {Hallucination Helps: Energy Efficient Virtual Circuit Routing},
	journal   = {{SIAM} J. Comput.},
	volume    = {49},
	number    = {1},
	pages     = {37--66},
	year      = {2020},
	url       = {https://doi.org/10.1137/18M1228591},
	doi       = {10.1137/18M1228591},
	timestamp = {Thu, 19 Mar 2020 10:23:55 +0100},
	biburl    = {https://dblp.org/rec/journals/siamcomp/AntoniadisIKMNP20.bib},
	bibsource = {dblp computer science bibliography, https://dblp.org}
}


@inproceedings{GuptaKKP19,
  author    = {Anupam Gupta and
               Ravishankar Krishnaswamy and
               Amit Kumar and
               Debmalya Panigrahi},
  title     = {Elastic Caching},
  booktitle = {Thirtieth Annual {ACM-SIAM} Symposium on Discrete
               Algorithms, {SODA}},
  year      = {2019}
}


@inproceedings{nips2019,
	author    = {Devvrit and Rohan Kadekodi and Ravishankar Krishanswamy and Harsha Simhadri and Suhas Jayaram Subramanya},
	title     = {Rand-NSG: Billion Point Nearest Neighbor Search on a Single Node},
	booktitle = {33rd Annual Conference on Neural Information Processing Systems NeurIPS },
year      = {2019}
}

@inproceedings{DevvritKR19,
  author    = {Devvrit and
               Ravishankar Krishnaswamy and
               Nived Rajaraman},
  title     = {Robust Correlation Clustering},
  booktitle = {33rd Annual Workshop on Approximation Algorithms APPROX},
  year      = {2019}
}


@inproceedings{KrishnaswamyLS18,
  author    = {Ravishankar Krishnaswamy and Shi Li and Sai Sandeep},
  title     = {A constant-factor approximation for $k$-median and $k$-means with outliers},
  booktitle = {50th Symposium on Theory of Computing, {STOC}},
  year      = {2018}
}

@article{EneCKP18,
  author    = {Alina Ene and
               Deeparnab Chakrabarty and
               Ravishankar Krishnaswamy and
               Debmalya Panigrahi},
  title     = {Online Buy-at-Bulk Network Design},
  journal   = {{SIAM} J. Comput.},
  volume    = {47},
  number    = {4},
  pages     = {1505-1528},
  year      = {2018},
}


@inproceedings{ChakrabartyKK17,
  author    = {Deeparnab Chakrabarty and
                            Ravishankar Krishnaswamy and Amit Kumar},
  title     = {The Heterogeneous Capacitated k-Center Problem},
  booktitle = {19th conference on Integer Programming and Combinatorial Optimization {IPCO}},
  year      = {2017}
}

@inproceedings{RaghunathanJK17,
  author    = {Aditi Raghunathan and
                            Prateek jain and Ravishankar Krishnaswamy},
  title     = {Learning Mixtures of Gaussians with Streaming Data},
  booktitle = {31st Annual Conference on Neural Information Processing Systems NeurIPS },
  year      = {2017}
}



@inproceedings{GuptaKKP17,
  author    = {Anupam Gupta and
                            Ravishankar Krishnaswamy and Amit Kumar and Debmalya Panigrahi},
  title     = {Online and Dynamic Algorithms for Set Cover},
  booktitle = {49th Symposium on Theory of Computing, {STOC}},
  year      = {2017}
}


@incollection{Krishnaswamy16,
  author    = {Ravishankar Krishnaswamy},
  title     = {Broadcast Scheduling - Minimizing Average Response Time},
  booktitle = {Encyclopedia of Algorithms},
  pages     = {237--240},
  year      = {2016}
}


@inproceedings{ChakrabartyGK16,
  author    = {Deeparnab Chakrabarty and
               Prachi Goyal and
               Ravishankar Krishnaswamy},
  title     = {The Non-Uniform k-Center Problem},
  booktitle = {43rd International Colloquium on Automata, Languages, and Programming,
               {ICALP}},
  year      = {2016}
}

@inproceedings{AwasthiCKS16,
  author    = {Pranjal Awasthi and
               Moses Charikar and
               Ravishankar Krishnaswamy and
               Ali Kemal Sinop},
  title     = {Spectral Embedding of k-Cliques, Graph Partitioning and k-Means},
  booktitle = {Innovations in Theoretical
               Computer Science},
  year      = {2016}
}

@article{KrishnaswamyS16,
  author    = {Ravishankar Krishnaswamy and
               Maxim Sviridenko},
  title     = {Inapproximability of the Multilevel Uncapacitated Facility Location
               Problem},
  journal   = {{ACM} Trans. Algorithms},
  volume    = {13},
  number    = {1},
  pages     = {1:1--1:25},
  year      = {2016}
}

@article{GuptaKNR15,
  author    = {Anupam Gupta and
               Ravishankar Krishnaswamy and
               Viswanath Nagarajan and
               R. Ravi},
  title     = {Running Errands in Time: Approximation Algorithms for Stochastic Orienteering},
  journal   = {Math. Oper. Res.},
  volume    = {40},
  number    = {1},
  pages     = {56--79},
  year      = {2015}
}

@article{Krishnaswamy0NS15,
  author    = {Ravishankar Krishnaswamy and
               Amit Kumar and
               Viswanath Nagarajan and
               Yogish Sabharwal and
               Barna Saha},
  title     = {Facility Location with Matroid or Knapsack Constraints},
  journal   = {Math. Oper. Res.},
  volume    = {40},
  number    = {2},
  pages     = {446--459},
  year      = {2015}
}


@inproceedings{BansalGKPSS15,
  author    = {Nikhil Bansal and
               Anupam Gupta and
               Ravishankar Krishnaswamy and
               Kirk Pruhs and
               Kevin Schewior and
               Clifford Stein},
  title     = {A 2-Competitive Algorithm For Online Convex Optimization With Switching
               Costs},
  booktitle = {{APPROX/RANDOM}},
  year      = {2015}
}

@inproceedings{AwasthiCKS15,
  author    = {Pranjal Awasthi and
               Moses Charikar and
               Ravishankar Krishnaswamy and
               Ali Kemal Sinop},
  title     = {The Hardness of Approximation of Euclidean k-Means},
  booktitle = {31st International Symposium on Computational Geometry, SoCG},
  year      = {2015}
}

@inproceedings{EneCKP15,
  author    = {Alina Ene and
               Deeparnab Chakrabarty and
               Ravishankar Krishnaswamy and
               Debmalya Panigrahi},
  title     = {Online Buy-at-Bulk Network Design},
  booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS}},
  year      = {2015}
}

@inproceedings{AwasthiBCKVW15,
  author    = {Pranjal Awasthi and
               Afonso S. Bandeira and
               Moses Charikar and
               Ravishankar Krishnaswamy and
               Soledad Villar and
               Rachel Ward},
  title     = {Relax, No Need to Round: Integrality of Clustering Formulations},
  booktitle = {Innovations in Theoretical Computer
               Science, {ITCS}},
  year      = {2015}
}

@article{BansalKN14,
  author    = {Nikhil Bansal and
               Ravishankar Krishnaswamy and
               Viswanath Nagarajan},
  title     = {Better Scalable Algorithms for Broadcast Scheduling},
  journal   = {{ACM} Trans. Algorithms},
  volume    = {11},
  number    = {1},
  pages     = {3:1--3:24},
  year      = {2014}
}



@inproceedings{BansalCKL14,
  author    = {Nikhil Bansal and
               Moses Charikar and
               Ravishankar Krishnaswamy and
               Shi Li},
  title     = {Better Algorithms and Hardness for Broadcast Scheduling via a Discrepancy
               Approach},
  booktitle = {Twenty-Fifth Annual {ACM-SIAM} Symposium on Discrete
               Algorithms, {SODA}},
  year      = {2014}
}

@inproceedings{AntoniadisIKMNPS14,
  author    = {Antonios Antoniadis and
               Sungjin Im and
               Ravishankar Krishnaswamy and
               Benjamin Moseley and
               Viswanath Nagarajan and
               Kirk Pruhs and
               Cliff Stein},
  title     = {Hallucination Helps: Energy Efficient Virtual Circuit Routing},
  booktitle = {Twenty-Fifth Annual {ACM-SIAM} Symposium on Discrete
               Algorithms, {SODA}},
  year      = {2014}
}

@inproceedings{KrishnaswamyNPS14,
  author    = {Ravishankar Krishnaswamy and
               Viswanath Nagarajan and
               Kirk Pruhs and
               Cliff Stein},
  title     = {Cluster before you hallucinate: approximating node-capacitated network
               design and energy efficient routing},
  booktitle = {Symposium on Theory of Computing, {STOC}},
  year      = {2014}
}



@inproceedings{ChakrabartyKLN13,
  author    = {Deeparnab Chakrabarty and
               Ravishankar Krishnaswamy and
               Shi Li and
               Srivatsan Narayanan},
  title     = {Capacitated Network Design on Undirected Graphs},
  booktitle = {16th International Workshop, {APPROX}},
  year      = {2013}
}

@inproceedings{BhaskaraKTW13,
  author    = {Aditya Bhaskara and
               Ravishankar Krishnaswamy and
               Kunal Talwar and
               Udi Wieder},
  title     = {Minimum Makespan Scheduling with Low Rank Processing Times},
  booktitle = {Twenty-Fourth Annual {ACM-SIAM} Symposium on Discrete
               Algorithms, {SODA}},
  year      = {2013}
}

@inproceedings{BansalGKNPS12,
  author    = {Nikhil Bansal and
               Anupam Gupta and
               Ravishankar Krishnaswamy and
               Viswanath Nagarajan and
               Kirk Pruhs and
               Cliff Stein},
  title     = {Multicast Routing for Energy Minimization Using Speed Scaling},
  booktitle = {First Mediterranean Conference
               on Algorithms, MedAlg},
  year      = {2012}
}

@inproceedings{KrishnaswamyS12,
  author    = {Ravishankar Krishnaswamy and
               Maxim Sviridenko},
  title     = {Inapproximability of the multi-level uncapacitated facility location
               problem},
  booktitle = {Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
               Algorithms, {SODA}},
  year      = {2012}
}


@article{GuptaKR12,
  author    = {Anupam Gupta and
               Ravishankar Krishnaswamy and
               R. Ravi},
  title     = {Online and Stochastic Survivable Network Design},
  journal   = {{SIAM} J. Comput.},
  volume    = {41},
  number    = {6},
  pages     = {1649--1672},
  year      = {2012},
}



@inproceedings{GuptaIKMP12,
  author    = {Anupam Gupta and
               Sungjin Im and
               Ravishankar Krishnaswamy and
               Benjamin Moseley and
               Kirk Pruhs},
  title     = {Scheduling heterogeneous processors isn't as easy as you think},
  booktitle = {Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
               Algorithms, {SODA}},
  year      = {2012}
}

@inproceedings{GuptaKNR12,
  author    = {Anupam Gupta and
               Ravishankar Krishnaswamy and
               Viswanath Nagarajan and
               R. Ravi},
  title     = {Approximation algorithms for stochastic orienteering},
  booktitle = {Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
               Algorithms, {SODA}},
  year      = {2012}
}

@inproceedings{BhaskaraDKT12,
  author    = {Aditya Bhaskara and
               Daniel Dadush and
               Ravishankar Krishnaswamy and
               Kunal Talwar},
  title     = {Unconditional differentially private mechanisms for linear queries},
  booktitle = {44th Symposium on Theory of Computing Conference,
               {STOC}},
  year      = {2012}
}

@inproceedings{GuptaKP12,
  author    = {Anupam Gupta and
               Ravishankar Krishnaswamy and
               Kirk Pruhs},
  title     = {Online Primal-Dual for Non-linear Optimization with Applications to
               Speed Scaling},
  booktitle = {Approximation and Online Algorithms - 10th International Workshop,
               {WAOA}},
  year      = {2012}
}

@inproceedings{BansalKS11,
  author    = {Nikhil Bansal and
               Ravishankar Krishnaswamy and
               Barna Saha},
  title     = {On Capacitated Set Cover Problems},
  booktitle = {14th International Workshop, {APPROX}},
  year      = {2011}
}

@inproceedings{GuptaKMR11,
  author    = {Anupam Gupta and
               Ravishankar Krishnaswamy and
               Marco Molinaro and
               R. Ravi},
  title     = {Approximation Algorithms for Correlated Knapsacks and Non-martingale
               Bandits},
  booktitle = {52nd Annual Symposium on Foundations of Computer Science, {FOCS}},
  year      = {2011}
}

@inproceedings{KrishnaswamyKNSS11,
  author    = {Ravishankar Krishnaswamy and
               Amit Kumar and
               Viswanath Nagarajan and
               Yogish Sabharwal and
               Barna Saha},
  title     = {The Matroid Median Problem},
  booktitle = {Twenty-Second Annual {ACM-SIAM} Symposium on Discrete
               Algorithms, {SODA}},
  year      = {2011}
}




@inproceedings{SekarKGR10,
  author    = {Vyas Sekar and
               Ravishankar Krishnaswamy and
               Anupam Gupta and
               Michael K. Reiter},
  title     = {Network-wide deployment of intrusion detection and prevention systems},
  booktitle = {{ACM} CoNEXT},
  year      = {2010}
}

@inproceedings{GuptaKP10b,
  author    = {Anupam Gupta and
               Ravishankar Krishnaswamy and
               Kirk Pruhs},
  title     = {Nonclairvoyantly scheduling power-heterogeneous processors},
  booktitle = {International Green Computing Conference},
  year      = {2010}
}

@inproceedings{GuptaKP10,
  author    = {Anupam Gupta and
               Ravishankar Krishnaswamy and
               Kirk Pruhs},
  title     = {Scalably Scheduling Power-Heterogeneous Processors},
  booktitle = {Automata, Languages and Programming, 37th International Colloquium,
               {ICALP}},
  year      = {2010}
}

@inproceedings{BansalKN10,
  author    = {Nikhil Bansal and
               Ravishankar Krishnaswamy and
               Viswanath Nagarajan},
  title     = {Better Scalable Algorithms for Broadcast Scheduling},
  booktitle = {Automata, Languages and Programming, 37th International Colloquium,
               {ICALP}},
  year      = {2010}
}

@inproceedings{GuptaKR10,
  author    = {Anupam Gupta and
               Ravishankar Krishnaswamy and
               R. Ravi},
  title     = {Tree Embeddings for Two-Edge-Connected Network Design},
  booktitle = {Twenty-First Annual {ACM-SIAM} Symposium on Discrete
               Algorithms, {SODA}},
  year      = {2010}
}

@inproceedings{BansalGK10,
  author    = {Nikhil Bansal and
               Anupam Gupta and
               Ravishankar Krishnaswamy},
  title     = {A Constant Factor Approximation Algorithm for Generalized Min-Sum
               Set Cover},
  booktitle = {Twenty-First Annual {ACM-SIAM} Symposium on Discrete
               Algorithms, {SODA}},
  year      = {2010}
}

@inproceedings{GuptaIKMP10,
  author    = {Anupam Gupta and
               Sungjin Im and
               Ravishankar Krishnaswamy and
               Benjamin Moseley and
               Kirk Pruhs},
  title     = {Scheduling jobs with varying parallelizability to reduce variance},
  booktitle = {22nd Annual {ACM} Symposium on Parallelism
               in Algorithms and Architectures, {SPAA}},
  year      = {2010}
}


@inproceedings{GuptaKKS09,
  author    = {Anupam Gupta and
               Ravishankar Krishnaswamy and
               Amit Kumar and
               Danny Segev},
  title     = {Scheduling with Outliers},
  booktitle = {12th International Workshop, {APPROX}},
  year      = {2009}
}

@inproceedings{GuptaKR09,
  author    = {Anupam Gupta and
               Ravishankar Krishnaswamy and
               R. Ravi},
  title     = {Online and stochastic survivable network design},
  booktitle = {41st Annual {ACM} Symposium on Theory of Computing,
               {STOC}},
  year      = {2009}
}