54 citations · 160 across the 36 of their papers we have counts for
Showing 2010Show all
2 papers · 1 filter
cs.CC2010★ 2 cited
Integrality Gaps of Linear and Semi-definite Programming Relaxations for Knapsack
Anna R. Karlin, Claire Mathieu, C. Thach Nguyen
In this paper, we study the integrality gap of the Knapsack linear program in the Sherali- Adams and Lasserre hierarchies. First, we show that an integrality gap of 2 - ε persists…
cs.DS2010
Online Correlation Clustering
Claire Mathieu, Ocan Sankur, Warren Schudy
We study the online clustering problem where data items arrive in an online fashion. The algorithm maintains a clustering of data items into similarity classes. Upon arrival of v,…