85 citations · 237 across the 30 of their papers we have counts for
Showing 2019Show all
3 papers · 1 filter
cs.DS2019
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…
cs.DS2019★ 5 cited
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…
cs.DM2019★ 14 cited
Multi-Criteria Dimensionality Reduction with Applications to Fairness
Uthaipon Tantipongpipat, Samira Samadi, Mohit Singh +2
Dimensionality reduction is a classical technique widely used for data analysis. One foundational instantiation is Principal Component Analysis (PCA), which minimizes the average r…