For Full-Text 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
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2017/01/01
Online ISSN: 1745-1337
Type of Manuscript: LETTER
Category: Algorithms and Data Structures
clustering problem, online problem, competitive analysis, capacity constraints,
Full Text: PDF(55.4KB)>>
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.