IEICE TRANSACTIONS on Fundamentals
Online Unit Clustering with Capacity Constraints
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E100-A No.1 pp.301-303
- Publication Date
- 2017/01/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E100.A.301
- Type of Manuscript
- LETTER
- Category
- Algorithms and Data Structures
Authors
Tetsuya ARAKI
the National Institute of Informatics
Koji M. KOBAYASHI
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Tetsuya ARAKI, Koji M. KOBAYASHI, "Online Unit Clustering with Capacity Constraints" in IEICE TRANSACTIONS on Fundamentals,
vol. E100-A, no. 1, pp. 301-303, January 2017, doi: 10.1587/transfun.E100.A.301.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E100.A.301/_p
Copy
@ARTICLE{e100-a_1_301,
author={Tetsuya ARAKI, Koji M. KOBAYASHI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Online Unit Clustering with Capacity Constraints},
year={2017},
volume={E100-A},
number={1},
pages={301-303},
abstract={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.},
keywords={},
doi={10.1587/transfun.E100.A.301},
ISSN={1745-1337},
month={January},}
Copy
TY - JOUR
TI - Online Unit Clustering with Capacity Constraints
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 301
EP - 303
AU - Tetsuya ARAKI
AU - Koji M. KOBAYASHI
PY - 2017
DO - 10.1587/transfun.E100.A.301
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E100-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 2017
AB - 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.
ER -
English
