5 papers · 1 filter
Optimal High Probability Bounds for Random Order Online Sorting
Chenglin Fan, Mingyu Kang
In random order online sorting, a fixed multiset of real numbers arrives in a uniformly random order. Each value must be placed immediately and irrevocably into an empty positi…
Pseudometric-Weighted Correlation Clustering via Spectral Preclustering
Chenglin Fan, Dahoon Lee, Euiwoong Lee
We study pseudometric-weighted correlation clustering, where every pair of vertices carries a nonnegative disagreement weight and the weights satisfy the triangle inequality. For e…
1.64-Approximation for Chromatic Correlation Clustering via Chromatic Cluster LP
Dahoon Lee, Chenglin Fan, Euiwoong Lee
Chromatic Correlation Clustering (CCC) generalizes Correlation Clustering by assigning multiple categorical relationships (colors) to edges and imposing chromatic constraints on th…
Improved Approximation Algorithms for Chromatic and Pseudometric-Weighted Correlation Clustering
Chenglin Fan, Dahoon Lee, Euiwoong Lee
Correlation Clustering (CC) is a foundational problem in unsupervised learning that models binary similarity relations using labeled graphs. While classical CC has been widely stud…
A PTAS for -Low Rank Approximation: Solving Dense CSPs over Reals
Vincent Cohen-Addad, Chenglin Fan, Suprovat Ghoshal +4
We consider the Low Rank Approximation problem, where the input consists of a matrix and an integer , and the goal is to find a matrix of…