Arranging Numbers on Circles to Reach Maximum Total Variations

Ying-Jie Liao, Min-Zheng Shieh, Shi-Chun Tsai

Abstract


The dartboard problem is to arrange $n$ numbers on a circle to obtain maximum risk, which is the sum of the $q$-th power of the absolute differences of adjacent numbers, for $q\ge 1$. Curtis showed that the dartboard problem admits a greedy algorithm. We generalize the dartboard problem by considering more circles and the goal is to arrange $kn$ number on $k$ circles to obtain the maximum risk. In this paper, we characterize an optimal arrangement for $k=2$ and show that the generalized dartboard problem also admits a greedy algorithm.


Full Text: PDF