3 papers
cs.DS2024
Online Load and Graph Balancing for Random Order Inputs
Sungjin Im, Ravi Kumar, Shi Li +2
Online load balancing for heterogeneous machines aims to minimize the makespan (maximum machine workload) by scheduling arriving jobs with varying sizes on different machines. In t…
cs.DS2024
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…
cs.DS2023
Handling Correlated Rounding Error via Preclustering: A 1.73-approximation for Correlation Clustering
Vincent Cohen-Addad, Euiwoong Lee, Shi Li +1
We consider the classic Correlation Clustering problem: Given a complete graph where edges are labelled either or , the goal is to find a partition of the vertices that mini…