Online Weight Balancing on the Unit Circle
Summary :
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 $ rac{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.
- Publication
- IEICE TRANSACTIONS on Information Vol.E99-D No.3 pp.567-574
- Publication Date
- 2016/03/01
- Publicized
- 2015/12/16
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.2015FCP0006
- Type of Manuscript
- Special Section PAPER (Special Section on Foundations of Computer Science---Developments of the Theory of Algorithms and Computation---)
- Category
Authors
Hiroshi FUJIWARA
Shinshu University
Takahiro SEKI
Computron Co., Ltd.
Toshihiro FUJITO
Toyohashi University of Technology
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
Hiroshi FUJIWARA, Takahiro SEKI, Toshihiro FUJITO, "Online Weight Balancing on the Unit Circle" in IEICE TRANSACTIONS on Information,
vol. E99-D, no. 3, pp. 567-574, March 2016, doi: 10.1587/transinf.2015FCP0006.
Abstract: 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 $ rac{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.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2015FCP0006/_p
Copy
@ARTICLE{e99-d_3_567,
author={Hiroshi FUJIWARA, Takahiro SEKI, Toshihiro FUJITO, },
journal={IEICE TRANSACTIONS on Information},
title={Online Weight Balancing on the Unit Circle},
year={2016},
volume={E99-D},
number={3},
pages={567-574},
abstract={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 $ rac{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.},
keywords={},
doi={10.1587/transinf.2015FCP0006},
ISSN={1745-1361},
month={March},}
Copy
TY - JOUR
TI - Online Weight Balancing on the Unit Circle
T2 - IEICE TRANSACTIONS on Information
SP - 567
EP - 574
AU - Hiroshi FUJIWARA
AU - Takahiro SEKI
AU - Toshihiro FUJITO
PY - 2016
DO - 10.1587/transinf.2015FCP0006
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E99-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2016
AB - 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 $ rac{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.
ER -
English
