Title: Dealing with Inconsistence: Some Recent Algorithmic Results on Clustering Problems
Abstract: The problem of achieving data consistency with the minimum amount ofmodifications has been studied in different areas, including machine learning, data mining, information retrieval, and computational biology. In this talk, we report our recent progress towards this research direction and present improved kernelization algorithms, parameterized algorithms, and approximation algorithms for clustering problems, including Cluster Editing, Hierarchical Clustering, and MaximumAgreementForest. We study the relationship between Cluster Editing and graph edge-cuts, and develop an efficient polynomial-time kernelization algorithm that produces a 2k-vertex kernel for the problem. The techniques also lead to an improved kernelization algorithm for the Hierarchical Clustering problem. Based on the study on the structures of a bottommost sibling set in a leaf-labeled tree, we develop the first fixed parameter tractable algorithm and the first constant-ratio approximation algorithm for the MaximumAgreementForest problem on unrootedmultifurcating trees.