Browsing by Author "Liao, Ying-Jie"

Now showing 1 - 1 of 1

Arranging numbers on circles to reach maximum total variations
(2007-06-28)
Liao, Ying-Jie
;
Shieh, Min-Zheng
;
Tsai, Shi-Chun
;
資訊工程學系
;
Department of Computer Science
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 >= 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.