Mohit Singh

Home       Publications       Thesis       Book       Teaching      


Associate Professor
H. Milton Stewart School of Industrial & Systems Engineering
Georgia Institute of Technology

Background

Research Interests

My research is in discrete optimization, approximation algorithms, convex optimization. My publications.

Professional Activities

Associate Editor, Mathematical Programming.
Organized Bellairs Workshop on Approximation Algorithms, 2011.
On Program Committees of SODA 2016, RANDOM 2015, MFCS 2014, FOCS 2013, APPROX 2013 , TAMC 2013, SODA 2010, SIAM Conference on Discrete Mathematics 2010. 
 
Contact

Email: mohitsinghr@gmail.com


Selected Publications (Complete List).

1. Approximating Minimum Bounded Degree Spanning Trees to within One of Optimal (joint work with Lap Chi Lau).
    Journal of ACM (JACM), 2015. A preliminary version appeared in the Proceedings of 39th ACM Symposium on Theory of Computing, STOC 2007.
We give an algorithm for the minimum bounded degree spanning tree problem that returns a tree of minimum cost while violating degree bounds by at most an addtive one. This is the optimal algorithm for this problem assuming P ≠ NP and proves a 15-year old conjecture of Goemans. The main technique we use is an iterative method. Also see my thesis and our book for more applications and details on the method.

2. A Randomized Rounding Approach to the Traveling Salesman Problem (joint work with Shayan Oveis Gharan and Amin Saberi).
    Proceedings of 52nd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2011 (Awarded Best Paper).
Given a connected graph what is the shortest tour that visits each vertex at least once? This problem is a special case of the traveling salesman problem and is known as graphical TSP. In this paper, we give an approximation algorithm for this problem achieving the first improvement over a classical result of Christofides from 1970's.

3. Entropy, Optimization and Counting (joint work with Nisheeth Vishnoi).
    Proceedings of 46th ACM Symposium on Theory of Computing (STOC 2014).
Given marginals of an unknown discrete probability distribution, the maximum entropy distribution is the one with maximum entropy satisfying these marginals. These distributions arise in many different areas including machine learning, statistical physics, economics and were crucial in designing approximation algorithms for the traveling salesman problem. In this paper, we show that the computation of these distributions is equivalent to a counting problem on the support of the distribution.

4. LP-based Algorithms for Capacitated Facility Location (joint work with Hyung-Chan An and Ola Svennson).
   Proceedings of 55th Annual Symposium on Foundations of Computer Science (FOCS 2014).
We give the first mathematical relaxation for the facility location problem which gives a constant factor approximation for the problem. This resolves one of the 10 open problems of Williamson and Shmoys.

5. Online Caching with Convex Costs (joint with Ishai Menache).
    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 (joint work with Vivek Narasayya, Ishai Menache, Feng Li, Manoj Syamala and Surajit Chaudhuri).
    Proceedings of 41st International Conference on Very Large Data Bases (VLDB), Vol. 8, no. 7, March 2015.
We consider the problem of memory manangement in cloud computing under a multi-tenant scenario. We design algorithms that generalize the Least Recently Used (LRU) algorithm in presence of convex cost functions. In the first paper, we give theoretical guarantees on the algorithm. In the second paper, we implement the algorithm and show computational results that shows that it outperforms others solutions on real systems.