Competitive Strategies for Online Clique Clustering

被引：3

作者：

Chrobak, Marek ^{[1
]}

Duerr, Christoph ^{[2
,3
]}

Nilsson, Bengt J. ^{[4
]}

机构：

[1] Univ Calif Riverside, Riverside, CA 92521 USA

[2] Univ Paris 06, Sorbonne Univ, UMR 7606, LIP6, Paris, France

[3] CNRS, UMR 7606, LIP6, Paris, France

[4] Malmo Univ, Dept Comp Sci, Malmo, Sweden

来源：

ALGORITHMS AND COMPLEXITY (CIAC 2015) | 2015年 / 9079卷

基金：

美国国家科学基金会;

关键词：

D O I：

10.1007/978-3-319-18173-8_7

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

A clique clustering of a graph is a partitioning of its vertices into disjoint cliques. The quality of a clique clustering is measured by the total number of edges in its cliques. We consider the online variant of the clique clustering problem, where the vertices of the input graph arrive one at a time. At each step, the newly arrived vertex forms a singleton clique, and the algorithm can merge any existing cliques in its partitioning into larger cliques, but splitting cliques is not allowed. We give an online strategy with competitive ratio 15.645 and we prove a lower bound of 6 on the competitive ratio, improving the previous respective bounds of 31 and 2.

引用

页码：101 / 113

页数：13

共 14 条

[1]

[Anonymous], 1998, Online Computation and Competitive Analysis

[2] Correlation clustering [J].