<p>If I understand your problem correctly, we can formulate it like so: given pairs $(\alpha_k,\beta_k)$ and $\Delta_0$, find $s &gt; 0$ such that $\max_k (s\alpha_k + \beta_k) = \Delta_0$. Here is one way to solve this (this algorithm can be made more efficient). Go over all possible $k$. For each $k$, find the value of $s$ such that $s\alpha_k + \beta_k = \Delta_0$ (namely $s = (\Delta_0 - \beta_k)/\alpha_k$), check that it's positive, and check that for all $l \leq k$, $s\alpha_l + \beta_l \leq \Delta_0$. This runs in $O(m^2)$, where $m$ is the number of pairs (in your case, $m = n(n-1)$); you can probably get the running time down to quasilinear. Your case is more structured, so you may be able to get an even faster algorithm.</p>

CC BY-SA 3.0
2013-09-06T17:54:44.720Z
2013-09-06T17:54:44.720Z
Yuval Filmus
<p>Suppose that we have $n \geq 2$ distinct triplets $t_0, t_1, ..., t_{n-1}$ of real numbers, $t_i = (x_i, l_i, r_i)$.</p>

<p>Define $$\Delta(s) = \max_{i, j} \left[ s (x_j - x_i) + (r_j - l_i) \right]$$</p>

<p>The problem is, given some arbitrary target $\Delta_0$, to find $s^*$ such that $\Delta(s^*) = \Delta_0$.  (NB: There may be no such $s^*$.  For example, $n = 2$, and $t_0 = (0, -1, 0), t_1 = (0, 0, 1)$, then $\Delta(s)$ has constant value $2$, so the problem has a solution, infinitely many in fact, only if $\Delta_0 = 2$.)</p>

<blockquote>
  <p>I'm looking for an algorithm to solve this problem, or at least some search terms (keywords, author names, etc) that I may try when searching online for such an algorithm.</p>
</blockquote>

<p>FWIW, for the special case I'm working with, the following additional conditions/considerations apply:</p>

<ol>
<li>$x_0 &lt; x_1$;</li>
<li>$l_0 = r_0 = l_1 = r_1 = 0$;</li>
<li>$l_i &lt; r_i, \forall \, i &gt; 1$;</li>
<li>only positive solutions $s^*$ are of interest;</li>
<li>$\Delta_0 \geq \max_{i,j} (r_j - l_i)$.</li>
</ol>

<ds.algorithms><optimization><convex-optimization>
Looking for algorithm (or at least name) for this optimization problem
kjo
# Looking for algorithm (or at least name) for this optimization problem

(Asked by: username_0 on 2013-09-06)

Suppose that we have $n \geq 2$ distinct triplets $t\_0, t\_1, ..., t\_{n-1}$ of real numbers, $t\_i = (x\_i, l\_i, r\_i)$.

Define $$\Delta(s) = \max\_{i, j} \left[ s (x\_j - x\_i) + (r\_j - l\_i) \right]$$

The problem is, given some arbitrary target $\Delta\_0$, to find $s^\*$ such that $\Delta(s^\*) = \Delta\_0$. (NB: There may be no such $s^\*$. For example, $n = 2$, and $t\_0 = (0, -1, 0), t\_1 = (0, 0, 1)$, then $\Delta(s)$ has constant value $2$, so the problem has a solution, infinitely many in fact, only if $\Delta\_0 = 2$.)

> I'm looking for an algorithm to solve this problem, or at least some search terms (keywords, author names, etc) that I may try when searching online for such an algorithm.

FWIW, for the special case I'm working with, the following additional conditions/considerations apply:

1. $x\_0 < x\_1$;
2. $l\_0 = r\_0 = l\_1 = r\_1 = 0$;
3. $l\_i < r\_i, \forall \, i > 1$;
4. only positive solutions $s^\*$ are of interest;
5. $\Delta\_0 \geq \max\_{i,j} (r\_j - l\_i)$.

**Tags:** ds.algorithms, optimization, convex-optimization

---

## 1 answers

### Answer by username_1 on 2013-09-06. Score: 3

If I understand your problem correctly, we can formulate it like so: given pairs $(\alpha\_k,\beta\_k)$ and $\Delta\_0$, find $s > 0$ such that $\max\_k (s\alpha\_k + \beta\_k) = \Delta\_0$. Here is one way to solve this (this algorithm can be made more efficient). Go over all possible $k$. For each $k$, find the value of $s$ such that $s\alpha\_k + \beta\_k = \Delta\_0$ (namely $s = (\Delta\_0 - \beta\_k)/\alpha\_k$), check that it's positive, and check that for all $l \leq k$, $s\alpha\_l + \beta\_l \leq \Delta\_0$. This runs in $O(m^2)$, where $m$ is the number of pairs (in your case, $m = n(n-1)$); you can probably get the running time down to quasilinear. Your case is more structured, so you may be able to get an even faster algorithm.


---

