Online Weight Balancing on the Unit Circle - Discrete and Computational Geometry and Graphs - page 76

As we demonstrated in the proof of Theorem 4 , C opt ( k ) = 0 holds if the place-
ment of k points can be decomposed into diameters and regular polygons. We
conjecture that the converse statement is also true. Note that, on the contrary,
the converse statement is false for the basic problem, as we discussed the case
k = 5 in Sect. 3.2 .

5 Concluding Remarks

Many questions are left open: What if arbitrary weights are allowed? Another
measure of balance? How about in

3 or an arbitrary metric space? (As intro-
duced, there are numerous studies on satellite constellation design such as [ 3 , 9 ].)
What if the destination of points is arbitrarily restricted? For the n -cyclotomic
problem, can a more sophisticated strategy be designed? Can the problem in
Sect. 4.2 be solved for general composite numbers? Does C opt ( k ) = 0 need the
placed points to be decomposed into diameters and regular polygons?

R

A cknowledgments. We would like to thank the participants of the 15th Enumeration
Algorithm Seminar held in Ikaho, Japan, for their helpful comments. This work was
supported by KAKENHI (23700014 and 23500014).

References

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 '13 (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 constel-
lations with the auction algorithm. Acta Astronaut. 62 (2-3), 112-130 (2008)
4. Karger, D., Lehman, E., Leighton, T., Panigrahy, R., Levine, M., Lewin, D.: Consis-
tent hashing and random trees: distributed caching protocols for relieving hot spots
on the world wide web. In: Proceedings of STOC '97, pp. 654-663 (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-16), 1203-1213 (1999)
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-151
(2007)
7. Teramoto, S., Asano, T., Katoh, N., Doerr, B.: Inserting points uniformly at every
instance. IEICE Trans. Inf. Syst. E89-D(8), 2348-2356 (2006)
8. Tignol, J.P.: Galois' Theory of Algebraic Equations. World Scientific Publishing
Company Incorporated, Singapore (2001)
9. Ulybyshev, Yu.: Design of satellite constellations with continuous coverage on elliptic
orbits of molniya type. Cosm. Res. 47 (4), 310-321 (2009)