6 papers
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…
On Tight FPT Time Approximation Algorithms for k-Clustering Problems
Han Dai, Shi Li, Sijin Peng
Following recent advances in combining approximation algorithms with fixed-parameter tractability (FPT), we study FPT-time approximation algorithms for minimum-norm -clustering…
Randomized Rounding over Dynamic Programs
Etienne Bamas, Shi Li, Lars Rohwedder
We show that under mild assumptions for a problem whose solutions admit a dynamic programming-like recurrence relation, we can still find a solution under additional packing constr…
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…
Learning-Augmented Streaming Algorithms for Correlation Clustering
Yinhao Dong, Shan Jiang, Shi Li +1
We study streaming algorithms for Correlation Clustering. Given a graph as an arbitrary-order stream of edges, with each edge labeled as positive or negative, the goal is to partit…
Complexity and Approximation Algorithms for Fixed Charge Transportation Problems
Yong Chen, Shi Li, Zihao Liang
The Fixed Charge Transportation (FCT) problem models transportation scenarios where we need to send a commodity from sources to sinks, and the cost of sending a commodity f…