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.

Published
2007-06-28
Article Number
R47