10 citations · 11 across the 3 of their papers we have counts for
6 papers
A Better-than-2 Approximation for k-Median Part I: The Power of General Bids
Rares-Darius Buhai, Vincent Cohen-Addad, Henry Fleischmann +6
The Greedy algorithm of Jain, Mahdian, Markakis, Saberi, and Vazirani was the best Lagrangian-multiplier-preserving (LMP) approximation algorithm for facility location, and thus th…
A Better-than- Approximation for -Median Part II: Stable Instances
Rares-Darius Buhai, Vincent Cohen-Addad, Henry Fleischmann +6
We consider the -median problem on general metric spaces, subject to the condition that the instances are -stable (i.e., the optimal solution using centers has a cost a…
Second Price Matching with Complete Allocation and Degree Constraints
Rom Pinchasi, Neta Singer, Lukas Vogl +1
We study the Second Price Matching problem, introduced by Azar, Birnbaum, Karlin, and Nguyen in 2009. In this problem, a bipartite graph (bidders and goods) is given, and the profi…
Static to Dynamic Correlation Clustering
Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee +7
Correlation clustering is a well-studied problem, first proposed by Bansal, Blum, and Chawla [Mach. Learn. '04]. The input is an unweighted, undirected graph. The problem is to clu…
Solving the Correlation Cluster LP in Sublinear Time
Nairen Cao, Vincent Cohen-Addad, Shi Li +7
Correlation Clustering is a fundamental and widely-studied problem in unsupervised learning and data mining. The input is a graph and the goal is to construct a clustering minimizi…
Understanding the Cluster LP for Correlation Clustering
Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee +3
In the classic Correlation Clustering problem introduced by Bansal, Blum, and Chawla (FOCS 2002), the input is a complete graph where edges are labeled either or , and the g…