Competitive Online Clique Clustering

DSpace Repository

Competitive Online Clique Clustering

Details

Files for download
Icon
Author manuscript
Overview of item record
Publication Paper in proceeding
Title Competitive Online Clique Clustering
Author Fabijan, Aleksander ; Nilsson, Bengt J. ; Persson, Mia
Editor Spirakis, Paul ; Serna, Maria
Date 2013
English abstract
Clique clustering is the problem of partitioning a graph into cliques so that some objective function is optimized. In online clustering, the input graph is given one vertex at a time, and any vertices that have previously been clustered together are not allowed to be separated. The objective here is to maintain a clustering the never deviates too far in the objective function compared to the optimal solution. We give a constant competitive upper bound for online clique clustering, where the objective function is to maximize the number of edges inside the clusters. We also give almost matching upper and lower bounds on the competitive ratio for online clique clustering, where we want to minimize the number of edges between clusters. In addition, we prove that the greedy method only gives linear competitive ratio for these problems.
Conference
8th International Conference on Algorithms and Complexity (May 22 - 24, 2013 : Barcelona, Spain)
DOI https://doi.org/10.1007/978-3-642-38233-8_19 (link to publisher's fulltext.)
Publisher Springer
Host/Issue Proceedings of the 8th International Conference on Algorithms and Complexity;8
Series/Issue Lecture Notes in Computer Science; 7878
ISSN 0302-9743
Pages 221-233
Language eng (iso)
Subject online algorithms
competitive analysis
clustering algorithms
Technology
Research Subject Categories::TECHNOLOGY
Note 8th International Conference on Algorithms and Complexity, Barcelona (... (see Details for more)
Handle http://hdl.handle.net/2043/16064 Permalink to this page
Link http://albcom.lsi.upc.edu/ciac2013/... (external link to related web page)
Facebook

This item appears in the following Collection(s)

Details

Search


Browse

My Account

Statistics