The circular balancing problem

Abstract

We propose a balancing problem with a minmax objective in a circular setting. This balancing problem involves the arrangement of an even number of items with different weights on a circle while minimizing the maximum total weight of items arranged on any half circle. Due to its generic structure, it may have applications in fair resource allocation schemes. We show the NP-hardness of the problem and develop polynomial-time algorithms when the number of distinct weights is a fixed constant. We propose for the general case a tight 7/6-approximation algorithm and show that it performs better than two existing algorithms designed for an equivalent problem in the literature. The worst-case performance ratio is derived through a linear combination of valid inequalities that are obtained from the problem definition, the properties of the proposed algorithm, and the optimal circular permutation structure. Furthermore, we formulate a more general problem of minimizing the maximum total weight of items on equally divided circular sectors and present its computational complexity and a tight approximation algorithm.