We are given an increasing sequence $S$ of positive real numbers $x\_1, x\_2, \ldots, x\_n$, such that $$x\_{i+2}-x\_{i+1} \ge c\,(x\_{i+1}-x\_i)$$ for all $i=1, 2, \ldots n-2$, where $c\ge 1$ is constant. Each number $x\_i\in S$ is associated with a positive integer weight $w\_i$ for all $i=1, 2, \ldots, n$. Let $W$ be the sequence formed by these weights.


Finally, let $$A=\sum\_{1\le i < j < k\le n} w\_i w\_j w\_k(x\_j-x\_i)~,$$ and $$B=\sum\_{1\le i < j < k\le n} w\_i w\_j w\_k\min(x\_k-x\_j, x\_j-x\_i)~.$$




---


**Question**: What is the minimum value for $c$ such that, *for all $S$ and* $W$, we have $A \le 2B~$? (*I am also interested in tight upper bounds*).




---




---


***Conjectures***: *I believe that $c\ge \frac{3}{2}$ is a sufficient condition to obtain $A \le 2B$ as required (I do not know whether it is also necessary). Furthermore, I think that the worst case w.r.t. $W$ occurs when $w\_{n}\gg n$ and $w\_{n-1} \gg n$, while all the other weights $w\_1, w\_2, \ldots, w\_{n-2}$ are equal to $1$. Finally, I also conjecture that, for any $\alpha\ge 2$, $c\ge 1+\frac{1}{\alpha}$ is a sufficient condition to obtain $A \le \alpha B$.*



Combinatorial optimization problem on sums of differences between real numbers
I will assume $c\le 2$, since that seems to be the case you are interested in. The argument below is formulated in terms of taking a given $c$ and computing the optimal $\alpha$, but this is equivalent to your question and the result agrees with your conjecture.


Step 1: We can change the formulation of the question so that the weights can be any nonnegative real numbers. Say we have such weights. We can always convert them to positive integer weights while changing
$$\frac{A}{B}$$
by arbitrarily small $\epsilon$. To do this, we approximate the real numbers by positive rational numbers, then scale all weights up by a large constant factor to make them all positive integers.


Step 2: We now pick some specific $1\le i<j<k\le n$ and set $w\_i=w\_j=w\_k=1$ and set all other weights to $0$. Then
$$\frac{A}{B}=\max\left(1,\frac{x\_j-x\_i}{x\_k-x\_j}\right)$$.
Note that for $\ell<j$, we have
$$
x\_{\ell+1}-x\_\ell\le \frac{x\_{j+1}-x\_j}{c^{j-\ell}}\le\frac{x\_k-x\_j}{c^{j-\ell}}
$$
with equality achieved when $k=j+1$ and all the ratios of successive differences are exactly $c$.


Then
$$
x\_j-x\_i=\sum\_{\ell=i}^{j-1}x\_{\ell+1}-x\_\ell\le \sum\_{\ell=i}^{j-1}\frac{x\_k-x\_j}{c^{j-\ell}}=(x\_k-x\_j)\sum\_{a=1}^{j-1}\frac{1}{c^a}\le \frac{x\_k-x\_j}{c-1}
$$
where equality is never achieved, but can be achieved to within an error of $\epsilon$ by taking $k=j+1$, taking $j-i$ large, and making all the ratios of successive differences be exactly $c$.


Thus for the special case of $w\_i=w\_j=w\_k=1$ and all other weights being $0$, we have
$$\frac{A}{B}\le \frac{1}{c-1}$$ and the bound is tight.


Step 3: Now if we allow arbitrary weights, we have that termwise the same inequality holds, that is
$$
w\_iw\_jw\_k(x\_j-x\_i)\le \frac{1}{c-1}w\_iw\_jw\_k\min(x\_j-x\_i,x\_k-x\_j)
$$
and summing, we get
$$
A\le \frac{1}{c-1}B
$$


