2022-08-11T03:32:47Zhttps://soar-ir.repo.nii.ac.jp/oaioai:soar-ir.repo.nii.ac.jp:000195652021-10-12T00:43:25Z1221:1222Online Weight Balancing on the Unit CircleFujiwara, HiroshiSeki, TakahiroFujito, Toshihiroonline algorithmcompetitive analysiscomputational geometryonline optimizationWe 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.ArticleIEICE TRANSACTIONS ON INFORMATION AND SYSTEMS. E99D(3): 567-574 (2016)journal articleIEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG2016application/pdfIEICE TRANSACTIONS ON INFORMATION AND SYSTEMS3E99D5675740916-8532https://soar-ir.repo.nii.ac.jp/record/19565/files/E99.D_2015FCP0006.pdfeng10.1587/transinf.2015FCP0006https://doi.org/10.1587/transinf.2015FCP0006copyrightÂ©2016 IEICE