
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Online Unit Clustering with Capacity Constraints
Tetsuya ARAKI Koji M. KOBAYASHI
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E100A
No.1
pp.301303 Publication Date: 2017/01/01
Online ISSN: 17451337
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)>>
Summary:
The online unit clustering problem is one of the most basic clustering problems proposed by Chan and ZarrabiZadeh (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.

