<p>Arrange $\{1,2,\cdots,n\}$ on a circle. What are the arrangements that minimize the maximal sum of all adjacent $k$ integers? For specific and low $n$'s it has been pointed out <a href="https://math.stackexchange.com/q/2826447/64809">in math.stackexchange.com</a> this problem can be solved with the binary linear programming. I would like to know if there are general solution for arbitrary $(n,k)$. A random algorithm that gives a probabilistic bound would be great, too.</p>

CC BY-SA 4.0
2018-06-23T21:09:33.863Z
An easy lower bound is $\lceil k(n+1)/2\rceil$ (as, for any arrangement, $k(n+1)/2$ is the average, over all sets of $k$ adjacent integers, of their sum).  An upper bound, for even $k$, appears to be $k(n+2)/2$, obtained by e.g. $1, n, 2, n-1, 3, n-2, \ldots, n/2-1, n/2$ (for even $n$).  For $k$ even this upper bound exceeds the lower bound by $k/2$.  For the special case of $k=2$ the upper bound is tight (as $n$ must be next to a number 2 or larger.)  How precise do you need your bounds to be?
Neal Young
CC BY-SA 4.0
2018-06-23T23:52:10.430Z
Yes, I should have mentioned these easy bounds. I have also tried other simple strategies. I would like to have tighter bounds which presumably require more sophisticated strategies or techniques. It is hard to say exactly how tight the bound I would like except the tighter the better. How about I ask if $\lfloor k(n+1)/2\rfloor+c$ for some constant is an upper bound?
Hans
CC BY-SA 4.0
2018-06-24T04:54:11.153Z
For how large a value of $n,k$ do you want to be able to solve this?
D.W.
CC BY-SA 4.0
2018-06-24T07:21:00.330Z
@D.W.: The best is for arbitrary $(n,k)$ but if you have an asymptotic result or tight bounds for large $(n,k)$ would be great too. If there is a general pattern or property the optimal arrangement would take on, that would be nice as well. In general, any interesting results are welcome.
Hans
CC BY-SA 4.0
2018-06-24T17:21:32.093Z
When $n=2k$ and $k$ is odd the answer is $\lceil k(n+1)/2\rceil = k(n+1)/2+1/2$.  The upper bound can be obtained by any arrangement where each odd position $i$ on the circle has some odd number $j$, and its antipodal position $(i+k) \bmod n$ has even number $j+1$.  When $n=ka$ and $a$ and $k$ are relatively prime, I think a generalization of this construction gives an upper bound of about $k(n+1)/2 + k'(a - k')/2$ where $k' = k \bmod a$.  The additive "error" term $k'(a-k')/2$ is between $(a-1)/2$ and $a^2/8$, so is constant when $a$ is constant.
Neal Young
CC BY-SA 4.0
2018-06-25T16:19:55.807Z
@NealYoung: Cool. Let me check your result out later. Thank you.
Hans
<ds.algorithms><optimization><randomized-algorithms>
Minimization of the maximal adjacent integer sums on a circle
Hans
# Minimization of the maximal adjacent integer sums on a circle

(Asked by: username_0 on 2018-06-23)

Arrange $\{1,2,\cdots,n\}$ on a circle. What are the arrangements that minimize the maximal sum of all adjacent $k$ integers? For specific and low $n$'s it has been pointed out [in math.stackexchange.com](https://math.stackexchange.com/q/2826447/64809) this problem can be solved with the binary linear programming. I would like to know if there are general solution for arbitrary $(n,k)$. A random algorithm that gives a probabilistic bound would be great, too.

**Tags:** ds.algorithms, optimization, randomized-algorithms
> **Comments:**
> **username_1**: An easy lower bound is $\lceil k(n+1)/2\rceil$ (as, for any arrangement, $k(n+1)/2$ is the average, over all sets of $k$ adjacent integers, of their sum).  An upper bound, for even $k$, appears to be $k(n+2)/2$, obtained by e.g. $1, n, 2, n-1, 3, n-2, \ldots, n/2-1, n/2$ (for even $n$).  For $k$ even this upper bound exceeds the lower bound by $k/2$.  For the special case of $k=2$ the upper bound is tight (as $n$ must be next to a number 2 or larger.)  How precise do you need your bounds to be?  
> **username_0**: Yes, I should have mentioned these easy bounds. I have also tried other simple strategies. I would like to have tighter bounds which presumably require more sophisticated strategies or techniques. It is hard to say exactly how tight the bound I would like except the tighter the better. How about I ask if $\lfloor k(n+1)/2\rfloor+c$ for some constant is an upper bound?  
> **username_2**: For how large a value of $n,k$ do you want to be able to solve this?  
> **username_0**: @D.W.: The best is for arbitrary $(n,k)$ but if you have an asymptotic result or tight bounds for large $(n,k)$ would be great too. If there is a general pattern or property the optimal arrangement would take on, that would be nice as well. In general, any interesting results are welcome.  
> **username_1**: When $n=2k$ and $k$ is odd the answer is $\lceil k(n+1)/2\rceil = k(n+1)/2+1/2$.  The upper bound can be obtained by any arrangement where each odd position $i$ on the circle has some odd number $j$, and its antipodal position $(i+k) \bmod n$ has even number $j+1$.  When $n=ka$ and $a$ and $k$ are relatively prime, I think a generalization of this construction gives an upper bound of about $k(n+1)/2 + k'(a - k')/2$ where $k' = k \bmod a$.  The additive "error" term $k'(a-k')/2$ is between $(a-1)/2$ and $a^2/8$, so is constant when $a$ is constant.  
> **username_0**: @NealYoung: Cool. Let me check your result out later. Thank you.  

---

## 0 answers

