Mohit Singh
POST DOC RESEARCHER
.
Post-doctoral Researcher, Microsoft Research, New England, Cambridge, MA 02142 mohsingh@microsoft.com Tel: (857)-653-6336
I am a post-doctoral researcher at Microsoft Research, New England in Cambridge. I was a Ph.D. student in the ACO (Algorithms, Combinatorics and Optimization) program at Tepper School of Business where my advisor was Prof. R. Ravi. I am interested in designing efficient algorithms for hard combinatorial optimization problems. My focus has been to design approximation algorithms for basic network design problems. I am also interested in studying models which deal with uncertainty in data including online algorithms, stochastic and robust optimization.
Publications
- Fabrizio Grandoni, Anupam Gupta, Stefano Leonardi, Pauli Miettinen, Piotr Sankowski, and Mohit Singh, Set Covering with our Eyes Closed, in 49th Annual IEEE Symposium on Foundations of Computer Science, October 2008
- Uriel Feige and Mohit Singh, Edge Coloring and Decompositions of Weighted Graphs, in Algorithms - ESA 2008, 16th Annual European Symposium, Karlsruhe, Germany, September 15-17, 2008. Proceedings, Springer, September 2008
- Tamás Király, Lap Chi Lau, and Mohit Singh, Degree Bounded Matroids and Submodular Flows, in Integer Programming and Combinatorial Optimization, 13th International Conference, IPCO 2008, Bertinoro, Italy, May 26-28, 2008, Proceedings, Springer, June 2008
- Lap Chi Lau and Mohit Singh, Additive approximation for bounded degree survivable network design, in Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008, ACM, May 2008
- Mohit Singh, Iterative Methods in Combinatorial Optimization, May 2008
- Uriel Feige and Mohit Singh, Improved Approximation Ratios for Traveling Salesperson Tours and Paths in Directed Graphs, in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 10th International Workshop, APPROX 2007, and 11th International Workshop, RANDOM 2007, Princeton, NJ, USA, August 20-22, 2007, Proceedings, Springer, August 2007
- Lap Chi Lau, Joseph Naor, Mohammad R. Salavatipour, and Mohit Singh, Survivable network design with degree or order constraints, in Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007, ACM, May 2007
- Mohit Singh and Lap Chi Lau, Approximating minimum bounded degree spanning trees to within one of optimal, in Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007, ACM, May 2007
- R. Ravi and Mohit Singh, Delegate and Conquer: An LP-Based Approximation Algorithm for Minimum Degree MSTs, in Automata, Languages and Programming, 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part I, Springer, July 2006
- Daniel Golovin, Viswanath Nagarajan, and Mohit Singh, Approximating the k -multicut problem, in SODA, ACM Press, January 2006
- Kedar Dhamdhere, R. Ravi, and Mohit Singh, On Two-Stage Stochastic Minimum Spanning Trees, in Integer Programming and Combinatorial Optimization, 11th International IPCO Conference, Berlin, Germany, June 8-10, 2005, Proceedings, Springer, 2005
- Kedar Dhamdhere, Vineet Goyal, R. Ravi, and Mohit Singh, How to Pay, Come What May: Approximation Algorithms for Demand-Robust Covering Problems, in FOCS, IEEE Computer Society, 2005
- Vittorio Bilò, Vineet Goyal, R. Ravi, and Mohit Singh, On the Crossing Spanning Tree Problem, in Approximation, Randomization, and Combinatorial Optimization, Algorithms and Techniques, 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2004, and 8th International Workshop on Randomization and Computation, RANDOM 2004, Cambridge, MA, USA, August 22-24, 2004, Proceedings, Springer, 2004
