Online Weight Balancing on the Unit Circle

• FUJIWARA Hiroshi

  Department of Computer Science & Engineering, Shinshu University

• SEKI Takahiro

  Computron Co., Ltd.

• FUJITO Toshihiro

  Department of Computer Science and Engineering, Toyohashi University of Technology

抄録

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 $\mathbb{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 $\frac{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.

収録刊行物

• IEICE Transactions on Information and Systems

  IEICE Transactions on Information and Systems E99.D (3), 567-574, 2016

  一般社団法人 電子情報通信学会

キーワード

• online algorithm
• competitive analysis
• computational geometry
• online optimization

詳細情報

• CRID: 1390282679354139776
• NII論文ID: 130005131814
• DOI: 10.1587/transinf.2015fcp0006
• ISSN: 17451361
• ISSN: 09168532
• HANDLE: 10091/00020326
• Web Site: https://soar-ir.repo.nii.ac.jp/records/19565
• Web Site: https://www.jstage.jst.go.jp/article/transinf/E99.D/3/E99.D_2015FCP0006/_pdf
• 本文言語コード: en
• データソース種別:
  • JaLC
  • IRDB
  • Crossref
  • CiNii Articles
  • KAKEN
• 抄録ライセンスフラグ: 使用不可