2023-01-29T15:23:33Z
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
copyrightÂ©2016 IEICE
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)
IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG
2016
eng
journal article
VoR
http://hdl.handle.net/10091/00020326
https://soar-ir.repo.nii.ac.jp/records/19565
https://doi.org/10.1587/transinf.2015FCP0006
10.1587/transinf.2015FCP0006
0916-8532
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS
E99D
3
567
574
https://soar-ir.repo.nii.ac.jp/record/19565/files/E99.D_2015FCP0006.pdf
application/pdf
388.1 kB
2018-03-09