Say we want to place n items on the real line. Let us denote the position of item i by $p_i$. We have interval constraints on the position $p_i$, i.e. we are given $l_i, r_i$ such that $l_i \le p_i \le r_i$. My problem is: given a specific item s, what is the maximum gap possible to the right of s? By maximum gap to the right of s I mean the distance between s and the next item to its right.
Mathematical Description:
More formally, I want to find $$f(s) = \max_{p_1,\dots,p_n} p_t - p_s$$ subject to \begin{align*} 1)\,& l_i \le p_i \le r_i\, \forall\,i \in [n] \\ 2)\,& \forall\,i\ne s,t: p_i \le p_s \text{ or }p_i \ge p_t \text{ (there is no item between s and t)} \end{align*}
In the absence of the second constraint the problem would have been a linear program. The second constraint makes it difficult.
Is this a known problem? Is it hard? Is there a dynamic programming solution? I am stuck because I don't know how to formulate the ordering of the items.
Thanks!
You can model the second constraint with binary variables : $$ p_i \le p_s + M(1-y_{is})\\ p_i \ge p_t - My_{is}\\ y_{is} \in \{0,1\} $$