Mohit Singh
—————————————————————————————————————————————————————————————————————————
I am a post-doctoral candidate 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. ————————————————————————————————————————————————————————————————————————— Teaching 47-853 Special Topics in Combinatorial Optimization Thesis Iterative Methods in Combinatorial Optimization ————————————————————————————————————————————————————————————————————————— Publications 1. Fabrizio Grandoni, Anupam Gupta, Stefano Leonardi, Pauli Miettinen, Piotr Sankowski and Mohit Singh, Set Covering with Our Eyes Closed, In Proceedings of 49th Annual Symposium on Foundations of Computer Science Conference, FOCS 2008. 2. Uriel Feige and Mohit Singh, Edge Coloring and Decompositions of Weighted Graphs, In Proceedings of European Symposium of Algorithms, ESA 2008: 405-416. 3. Lap Chi Lau and Mohit Singh, Additive Approximation for Bounded Degree Survivable Network Design, Appeared in 40th ACM Symposium on Theory of Computing, STOC 2008. 4. Tamas Kiraly, Lap Chi Lau and Mohit Singh, Degree Bounded Matroids and Submodular Flows, Appeared in 13th Conference on Integer Programming and Combinatorial Optimization, IPCO 2008. 5. Uriel Feige and Mohit Singh Improved Approximation Ratios for Traveling Salesperson Tours and Paths in Directed Graphs, Proceedings of 10th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2007. 6. Mohit Singh and Lap Chi Lau Approximating Minimum Bounded Degree Spanning Tress to within One of Optimal , Proceedings of 39th ACM Symposium on Theory of Computing, STOC 2007. 7. L.C. Lau, S. Naor, M. Salavatipour and M. Singh Survivable Network Design with Degree or Order Constraints, Proceedings of 39th ACM Symposium on Theory of Computing, STOC 2007. 8. R. Ravi and Mohit Singh, Delegate and Conquer: An LP-based Approximation Algorithms for Minimum Degree MSTs, Proceedings of 33rd International Colloquium on Automata, Languages and Programming, ICALP 2006: 169--180. 9. Daniel Golovin, Viswanath Nagarajan and Mohit Singh, Approximating the k-Multicut Problem, Proceedings of ACM-SIAM Symposium on Discrete Algorithms, SODA 2006: 621--630. 10. Kedar Dhamdere, Vineet Goyal, R. Ravi and Mohit Singh, How to Pay, Come What May: Approximation Algorithms for Demand-Robust Covering Problems, Proceedings of 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005: 367--378. 11. Kedar Dhamdere, R. Ravi and Mohit Singh, On Stochastic Minimum Spanning Trees, Proceedings of Eleventh Conference on Integer Programming and Combinatorial Optimization, IPCO 2005: 321--324. 12. Vittorio Bilo, Vineet Goyal, R. Ravi and Mohit Singh, On the Crossing Spanning Tree Problem, Proceedings of 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2004: 51--60. Latest Version.
|
