Online Unit Clustering with Capacity Constraints

Tetsuya ARAKI  Koji M. KOBAYASHI  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E100-A   No.1   pp.301-303
Publication Date: 2017/01/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E100.A.301
Type of Manuscript: LETTER
Category: Algorithms and Data Structures
Keyword: 
clustering problem,  online problem,  competitive analysis,  capacity constraints,  

Full Text: PDF(55.4KB)>>
Buy this Article




Summary: 
The online unit clustering problem is one of the most basic clustering problems proposed by Chan and Zarrabi-Zadeh (WAOA2007 and Theory of Computing Systems 45(3), 2009). Several variants of this problem have been extensively studied. In this letter, we propose a new variant of the online unit clustering problem, called the online unit clustering problem with capacity constraints. For this problem, we use competitive analysis to evaluate the performance of an online algorithm. Then, we develop an online algorithm whose competitive ratio is at most 3.178, and show that a lower bound on the competitive ratio of any online algorithm is 2.