2024-03-28T08:43:42Z
https://soar-ir.repo.nii.ac.jp/oai
oai:soar-ir.repo.nii.ac.jp:00019565
2022-12-14T04:31:02Z
1221:1222
Online Weight Balancing on the Unit Circle
Fujiwara, Hiroshi
Seki, Takahiro
Fujito, Toshihiro
online algorithm
competitive analysis
computational geometry
online optimization
We consider a problem as follows: Given unit weights arriving in an online manner with the total cardinality unknown, upon each arrival we decide where to place it on the unit circle in R-2. The objective is to set the center of mass of the placed weights as close to the origin as possible. We apply competitive analysis defining the competitive difference as a performance measure. We first present an optimal strategy for placing unit weights which achieves a competitive difference of 1/5. We next consider a variant in which the destination of each weight must be chosen from a set of positions that equally divide the unit circle. We give a simple strategy whose competitive difference is 0.35. Moreover, in the offline setting, several conditions for the center of mass to lie at the origin are derived.
Article
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS. E99D(3): 567-574 (2016)
journal article
IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG
2016
application/pdf
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS
3
E99D
567
574
0916-8532
https://soar-ir.repo.nii.ac.jp/record/19565/files/E99.D_2015FCP0006.pdf
eng
10.1587/transinf.2015FCP0006
https://doi.org/10.1587/transinf.2015FCP0006
copyright©2016 IEICE