For positive integers $n,m,k$, you're given a vector $c\in\mathbb{N}^n$ and a set $\Omega$ of $k$ finite non-empty sequences of numbers from $\{1,\dots,m\}$. You're asked to choose $\sigma_1\lt\sigma_2\lt\ldots\lt\sigma_\ell$ in $\{1,\ldots,n\}$ and $\varphi\colon\{1,\ldots,\ell\}\rightarrow\Omega$ such that, \begin{eqnarray} (1)\quad\forall i\in\{1,\ldots,\ell\},\quad \sigma_{i+1}-\sigma_i\ge |\varphi(i)| \end{eqnarray} then, you're rewarded $r$ dollars where,
\begin{equation} r = \sum_{1\le i\le\ell}\,\,\sum_{0\le j\lt|\varphi(i)|}c(i+j)\varphi(i)_j \end{equation} Question: is there a known algorithm for computing the max of $r$ over the choices of $\sigma$'s and $\varphi$?

Comments: In other terms, you're asked to build a vector $x\in\mathbb{N}^n$ where a subset of sequences in $\Omega$ are laid out in a non-overlapping fashion such that the inner product $c\cdot x$ is maximized (non-occupied site of $x$ are set to $0$). More precisely, you're asked to compute \begin{eqnarray} \max_x c\cdot x. \end{eqnarray}


  • $|\varphi(i)|$ denotes the length of the sequence $\varphi(i)$.
  • $\varphi(i)_j$ denotes the $j$-th term of the sequence $\varphi(i)$.
  • For correctness of $(1)$, let $\sigma_{\ell+1}=n+1$.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.