Item type |
学術雑誌論文 / Journal Article(1) |
公開日 |
2018-03-09 |
タイトル |
|
|
タイトル |
Online Weight Balancing on the Unit Circle |
言語 |
|
|
言語 |
eng |
DOI |
|
|
|
関連識別子 |
https://doi.org/10.1587/transinf.2015FCP0006 |
|
|
関連名称 |
10.1587/transinf.2015FCP0006 |
キーワード |
|
|
主題 |
online algorithm, competitive analysis, computational geometry, online optimization |
資源タイプ |
|
|
資源 |
http://purl.org/coar/resource_type/c_6501 |
|
タイプ |
journal article |
著者 |
Fujiwara, Hiroshi
Seki, Takahiro
Fujito, Toshihiro
|
信州大学研究者総覧へのリンク |
|
|
氏名 |
Fujiwara, Hiroshi |
|
URL |
http://soar-rd.shinshu-u.ac.jp/profile/ja.OmSVOFnU.html |
出版者 |
|
|
出版者 |
IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG |
引用 |
|
|
内容記述 |
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS. E99D(3): 567-574 (2016) |
書誌情報 |
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS
巻 E99D,
号 3,
p. 567-574,
発行日 2016
|
抄録 |
|
|
内容記述 |
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 |
ISSN |
|
|
収録物識別子タイプ |
ISSN |
|
収録物識別子 |
0916-8532 |
権利 |
|
|
権利情報 |
copyright©2016 IEICE |
出版タイプ |
|
|
出版タイプ |
VoR |
|
出版タイプResource |
http://purl.org/coar/version/c_970fb48d4fbd8a85 |
WoS |
|
|
URL |
http://gateway.isiknowledge.com/gateway/Gateway.cgi?&GWVersion=2&SrcAuth=ShinshuUniv&SrcApp=ShinshuUniv&DestLinkType=FullRecord&DestApp=WOS&KeyUT=000375973400003 |