10 citations · 27 across the 5 of their papers we have counts for
11 papers · 1 filter
Efficient Determinant Maximization for All Matroids
Adam Brown, Aditi Laddha, Madhusudhan Pittu +1
Determinant maximization provides an elegant generalization of problems in many areas, including convex geometry, statistics, machine learning, fair allocation of goods, and networ…
Maximizing Determinants under Matroid Constraints
Vivek Madan, Aleksandar Nikolov, Mohit Singh +1
Given vectors and a matroid , we study the problem of finding a basis of such that is maximized…
On the Unreasonable Effectiveness of the Greedy Algorithm: Greedy Adapts to Sharpness
Alfredo Torrico, Mohit Singh, Sebastian Pokutta
Submodular maximization has been widely studied over the past decades, mostly because of its numerous applications in real-world problems. It is well known that the standard greedy…
Integrality Gap of the Vertex Cover Linear Programming Relaxation
Mohit Singh
We give a characterization result for the integrality gap of the natural linear programming relaxation for the vertex cover problem. We show that integrality gap of the standard li…
Online and Offline Greedy Algorithms for Routing with Switching Costs
Roy Schwartz, Mohit Singh, Sina Yazdanbod
Motivated by the use of high speed circuit switches in large scale data centers, we consider the problem of circuit switch scheduling. In this problem we are given demands between…
Sticky Brownian Rounding and its Applications to Constraint Satisfaction Problems
Sepehr Abbasi-Zadeh, Nikhil Bansal, Guru Guruganesh +3
Semidefinite programming is a powerful tool in the design and analysis of approximation algorithms for combinatorial optimization problems. In particular, the random hyperplane rou…