Online Weight Balancing on the Unit Circle

详细信息    查看全文

• 作者：Hiroshi Fujiwara (16)
  Takahiro Seki (17)
  Toshihiro Fujito (16)
  
• 刊名：Lecture Notes in Computer Science
• 出版年：2014
• 出版时间：2014
• 年：2014
• 卷：1
• 期：1
• 页码：65-76
• 全文大小：474 KB
• 参考文献：1. Barba, L., De Carufel, J.L., Fleischer, R., Kawamura, A., Korman, M., Okamoto, Y., Tang, Y., Tokuyama, T., Verdonschot, S., Wang, T.: Geometric weight balancing. In: Proceedings of AAAC 鈥?3 (the 6th Annual Meeting of Asian Association for Algorithms and Computation), p. 31 (2013)
  2. Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press, Cambridge (1998)
  3. de Weck, O.L., Scialom, U., Siddiqi, A.: Optimal reconfiguration of satellite constellations with the auction algorithm. Acta Astronaut. 62(2鈥?), 112鈥?30 (2008) CrossRef
  4. Karger, D., Lehman, E., Leighton, T., Panigrahy, R., Levine, M., Lewin, D.: Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the world wide web. In: Proceedings of STOC 鈥?7, pp. 654鈥?63 (1997)
  5. Karger, D., Sherman, A., Berkheimer, A., Bogstad, B., Dhanidina, R., Iwamoto, K., Kim, B., Matkins, L., Yerushalmi, Y.: Web caching with consistent hashing. Comput. Netw. 31(11鈥?6), 1203鈥?213 (1999) CrossRef
  6. Kurebe, Y., Miwa, H., Ibaraki, T.: Juuryoutsuki module tsumekomino saitekika (optimization of the packing of weighted modules). In: Proceedings of the 2007 Spring National Conference of Operations Research Society of Japan, pp. 150鈥?51 (2007)
  7. Teramoto, S., Asano, T., Katoh, N., Doerr, B.: Inserting points uniformly at every instance. IEICE Trans. Inf. Syst. E89-D(8), 2348鈥?356 (2006)
  8. Tignol, J.P.: Galois鈥?Theory of Algebraic Equations. World Scientific Publishing Company Incorporated, Singapore (2001) CrossRef
  9. Ulybyshev, Yu.: Design of satellite constellations with continuous coverage on elliptic orbits of molniya type. Cosm. Res. 47(4), 310鈥?21 (2009) CrossRef
  
• 作者单位：Hiroshi Fujiwara (16)
  Takahiro Seki (17)
  Toshihiro Fujito (16)
  
  16. Toyohashi University of Technology, Toyohashi, Japan
  17. Computron Co. Ltd., Maebashi-shi, Japan
  
• ISSN：1611-3349

文摘

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.