85 citations · 237 across the 30 of their papers we have counts for
4 papers · 1 filter
Approximating Minimum Cost Connectivity Orientation and Augmentation
Mohit Singh, László A. Végh
We investigate problems addressing combined connectivity augmentation and orientations settings. We give a polynomial-time 6-approximation algorithm for finding a minimum cost subg…
Entropy, Optimization and Counting
Mohit Singh, Nisheeth K. Vishnoi
In this paper we study the problem of computing max-entropy distributions over a discrete set of objects subject to observed marginals. Interest in such distributions arises due to…
On the Approximation of Submodular Functions
Nikhil R. Devanur, Shaddin Dughmi, Roy Schwartz +2
Submodular functions are a fundamental object of study in combinatorial optimization, economics, machine learning, etc. and exhibit a rich combinatorial structure. Many subclasses…
An Improved Integrality Gap for Asymmetric TSP Paths
Zachary Friggstad, Anupam Gupta, Mohit Singh
The Asymmetric Traveling Salesperson Path Problem (ATSPP) is one where, given an asymmetric metric space with specified vertices s and t, the goal is to find an s-t path of…