Mohit Singh

Home Publications Book Teaching

Dynamic Resource Allocation in the Cloud with Near-Optimal Efficiency, Sebastian Perez-Salazar, Ishai Menache, Mohit Singh and Alejandro Toriello, To Appear in Operations Research, 2021.

Online Adaptive Bin Packing with Overflow, Sebastian Perez-Salazar, Mohit Singh and Alejandro Toriello, Arxiv 2020.

Maximizing Determinants under Matroid Constraints, Vivek Madan, Aleksandar Nikolov, Mohit Singh and Uthaipon Tantipongpipat, In Proceedings of 61st Annual Symposium on Foundations of Computer Science (FOCS) 2020.

On the Unreasonable Effectiveness of the Greedy Algorithm: Greedy Adapts to Sharpness, Alfredo Torrico, Mohit Singh and S Pokutta, In Proceedings of the 37th International Conference on Machine Learning (ICML) 2020.

Sticky Brownian Rounding and its Applications to Constraint Satisfaction Problems, S Abbasi-Zadeh, N Bansal, G Guruganesh, A Nikolov, R Schwartz, M. Singh, In Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA) 2020.

Multi-Criteria Dimensionality Reduction with Applications to Fairness, J Morgenstern, S Samadi, M Singh, U Tantipongpipat, S Vempala, In Proceedings of Advances in Neural Information Processing Systems (NeurIPS) 2019.

Integrality Gap of the Vertex Cover Linear Programming Relaxation, Mohit Singh, Operations Research Letters 47 (4), 288-290, 2019.

Online and Offline Greedy Algorithms for Routing with Switching Costs, R Schwartz, M Singh, S Yazdanbod, In Proceedings of Foundations of Software Technology and Theoretical Computer Science (FSTTCS) 2019.

Proportional Volume Sampling and Approximation Algorithms for A-Optimal Design, Aleksandar Nikolov, Mohit Singh, Uthaipon Tao Tantipongpipat, In Proceedings of 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) 2019.

Robust submodular maximization: Offline and online algorithms, Nima Anari, Nika Haghtalab, Sebastian Pokutta, Mohit Singh, Alfredo Torrico. In Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics (AISTATS) 2019.

Combinatorial Algorithms for Optimal Design, Vivek Madan, Mohit Singh, Uthaipon Tantipongpipat, Weijun Xie; Proceedings of the Thirty-Second Conference on Learning Theory (COLT), 2019.

The Price of Fair PCA: One Extra Dimension Samira Samadi, Uthaipon Tantipongpipat, Jamie Morgenstern, Mohit Singh, and Santosh Vempala, In Proceedings of Thirty-second Conference on Neural Information Processing Systems (NIPS) 2018.

Simple Graph Density Inequalities with no Sum of Squares Proofs, G Blekherman, A Raymond, M Singh, RR Thomas. Arxiv 2018.

Timing Matters: Online Dynamics in Broadcast Games Shuchi Chawla, Seffi Naor, Debmalya Panigrahi, Mohit Singh and Seeun William Umboh, In Proceedings of the 14th Conference on Web and Internet Economics (WINE), 2018.

Approximate Positively Correlated Distributions and Approximation Algorithms for D-optimal Design Mohit Singh, Weijun Xie. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) 2018.

Symmetric Sums of Squares over k-Subset Hypercubes, Annie Raymond, James Saunderson, Mohit Singh, Rekha R. Thomas. Math. Programming 167(2): 315-354 (2018).

Approximating Minimum Cost Connectivity Orientation and Augmentation Mohit Singh, Laszlo A. Vegh. SIAM J. Comput. 47(1): 270-293 (2018).
A preliminary version appeared in Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA) 2014.

k-Trails: Recognition, Complexity, and Approximations, Mohit Singh, Rico Zenklusen. Mathematical Programming 172 (1-2), 169-189, 2018.
A preliminary version appeared in the Proceedings of the 18th Conference on Integer Programming and Combinatorial Optimization (IPCO) 2016.

Efficient Algorithms for Discrepancy Minimization in Convex Sets, Ronen Eldan and Mohit Singh, Random Structures and Algorithms, 2018.

Symmetry in Turan Sums of Squares Polynomials from Flag Algebras, Annie Raymond, Mohit Singh, Rekha R. Thomas, Algebraic Combinatorics Volume 1 (2018) no. 2 p. 249-274.

LP-Based Algorithms for Capacitated Facility Location. Hyung-Chan An, Mohit Singh, Ola Svensson. SIAM J. Comput. 46(1): 272-306 (2017).
A preliminary version appeared in 55th Annual Symposium on Foundations of Computer Science (FOCS 2014).

Minimum Birkhoff-von Neumann Decomposition, Janardhan Kulkarni, Euiwoong Lee, Mohit Singh. In proceedings of 19th Integer Programming and Combinatorial Optimization (IPCO) 2017.

Nash Social Welfare, Matrix Permanent, and Stable Polynomials, Nima Anari, Shayan Oveis Gharan, Amin Saberi and Mohit Singh, In Proceedings of Innovations in Theoretical Computer Science (ITCS) 2017.

Random Walks in Polytopes and Negative Dependence, Yuval Peres, Mohit Singh and Nisheeth Vishnoi, In Proceedings of Innovations in Theoretical Computer Science (ITCS) 2017.

Maximizing determinants under partition constraints, Aleksandar Nikolov, Mohit Singh, In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (STOC) 2016.

An Improved Integrality Gap for Asymmetric TSP Paths Zachary Friggstad, Anupam Gupta and Mohit Singh. Math of Operation Research, Vol. 41, No. 3, pp. 745-757, August 2016.
A Preliminary version appeared in Proceedings of 16th International Conference on Integer Programming and Combinatorial Optimization IPCO 2013: 181-192.

A geometric alternative to Nesterov's accelerated gradient descent, Sebastien Bubeck, Yin Tat Lee, Mohit Singh, June 2015.

Online Caching with Convex Costs, Ishai Menache and Mohit Singh. To appear in Proceedings of 27th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), June 2015.

Sharing Buffer Pool Memory in Multi-Tenant Relational Database-as-a-Service, Vivek Narasayya, Ishai Menache, Mohit Singh, Feng Li, Manoj Syamala and Surajit Chaudhuri, In Proceedings of 41st International Conference on Very Large Data Bases (VLDB), Vol. 8, no. 7, March 2015.

Entropy, Optimization and Counting, Mohit Singh and Nisheeth Vishnoi. In Proceedings of 46th ACM Symposium on Theory of Computing (STOC 2014).

Discrepancy Without Partial Colorings, Nicholas J. A. Harvey, Roy Schwartz, Mohit Singh, In International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX'2014).

Short Tours through Large Linear Forests, Uriel Feige, R. Ravi and Mohit Singh, In Proceedings of 17th Conference on Integer Programming and Combinatorial Optimization (IPCO 2014).

New approaches to multi-objective optimization Fabrizio Grandoni, R. Ravi, Mohit Singh and Rico Zenklusen. Mathematical Programming (2014).

Approximation Algorithms for Online Weighted Rank Function Maximization under Matroid Constraints, Niv Buchbinder, Joseph Naor, R. Ravi, Mohit Singh, Automata, Languages, and Programming - 39th International Colloquium, ICALP (1) 2012: 145-156.

A Rounding by Sampling Approach to the Minimum Size k-Arc Connected Subgraph Problem, Bundit Laekhanukit, Shayan Oveis Gharan, Mohit Singh, Automata, Languages, and Programming - 39th International Colloquium, ICALP (1) 2012: 606-616.

A Randomized Rounding Approach to the Traveling Salesman Problem, Shayan Oveis Gharan, Amin Saberi and Mohit Singh, 52nd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2011: 550-559. Full version.

Online Node-weighted Steiner Tree and Related Problems. Seffi Naor, Debmalya Panigrahy and Mohit Singh, 52nd Annual IEEE Symposium on Foundations of Computer Science FOCS 2011: 210-219.

Approximation Algorithms for Online Submodular Function Maximization subject to a Matroid Constraint. Niv Buchbinder, Seffi Naor, R. Ravi and Mohit Singh, Submitted, 2010.

Incentives in Online Auctions via Linear Programming. Niv Buchbinder, Kamal Jain and Mohit Singh, In Proceedings of Sixth Workshop on Internet and Network Economics (WINE), 2010.

Improving Integrality Gaps via Chvatal-Gomory Rounding. Mohit Singh and Kunal Talwar, In Proceedings of the 13th Intl. Workshop on Approximation Algorithms for Combinatorial Optimization Problems - APPROX 2010.

Secretary Problems via Linear Programming. Niv Buchbinder, Kamal Jain and Mohit Singh, To Appear In Proceedings of the 14th Conference on Integer Programming and Combinatorial Optimization (IPCO), 2010.

Deploying Mesh Nodes under Non-Uniform Propagation. Joshua Robinson, Mohit Singh, R. Swaminathan, and E. Knightly, To Appear in Proceedings of IEEE INFOCOM 2010, San Diego, CA, March 2010.

Iterative Rounding for Multi-Objective Optimization Problems. Fabrizio Grandoni, R. Ravi, Mohit Singh, In Proceedings of European Symposium of Algorithms, ESA 2009: 95-106.

Set Covering with Our Eyes Closed. Fabrizio Grandoni, Anupam Gupta, Stefano Leonardi, Pauli Miettinen, Piotr Sankowski and Mohit Singh, In Proceedings of 49th Annual Symposium on Foundations of Computer Science Conference, FOCS 2008: 347-356.

Edge Coloring and Decompositions of Weighted Graphs. Uriel Feige and Mohit Singh, In Proceedings of European Symposium of Algorithms, ESA 2008: 405-416.

Additive Approximation for Bounded Degree Survivable Network Design. Lap Chi Lau and Mohit Singh, In Proceedings of 40th ACM Symposium on Theory of Computing, STOC 2008: 759-768.

Degree Bounded Matroids and Submodular Flows. Tamas Kiraly, Lap Chi Lau and Mohit Singh, In Proceedings of 13th Conference on Integer Programming and Combinatorial Optimization, IPCO 2008: 259-272.

Improved Approximation Ratios for Traveling Salesman Tours and Paths in Directed Graphs. Uriel Feige and Mohit Singh, In Proceedings of 10th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2007: 104-118.

Approximating Minimum Bounded Degree Spanning Trees to within One of Optimal. Mohit Singh and Lap Chi Lau, In Proceedings of 39th ACM Symposium on Theory of Computing, STOC 2007: 661-670.

Survivable Network Design with Degree or Order Constraints. Lap Chi Lau, S. Naor, M. Salavatipour and M. Singh, In Proceedings of 39th ACM Symposium on Theory of Computing, STOC 2007: 651-660. Journal Version SIAM Journal of Computing, Volume 39, Issue 3, 2009: 1062-1087.

Delegate and Conquer: An LP-based Approximation Algorithms for Minimum Degree MSTs. R. Ravi and Mohit Singh, In Proceedings of 33rd International Colloquium on Automata, Languages and Programming, ICALP 2006: 169--180.

Approximating the k-Multicut Problem. Daniel Golovin, Viswanath Nagarajan and Mohit Singh, In Proceedings of ACM-SIAM Symposium on Discrete Algorithms, SODA 2006: 621--630.

How to Pay, Come What May: Approximation Algorithms for Demand-Robust Covering Problems. Kedar Dhamdere, Vineet Goyal, R. Ravi and Mohit Singh, In Proceedings of 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005: 367--378.

On Stochastic Minimum Spanning Trees. Kedar Dhamdere, R. Ravi and Mohit Singh, In Proceedings of Eleventh Conference on Integer Programming and Combinatorial Optimization, IPCO 2005: 321--324.

On the Crossing Spanning Tree Problem,. Vittorio Bilo, Vineet Goyal, R. Ravi and Mohit Singh, In Proceedings of 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2004: 51--60. Latest Version.