Skip to main content
1 of 2
Tom Solberg
  • 4k
  • 12
  • 25

Minimizing square roots with the consecutive ones property

Let $A=[a_{ik}]$ be a matrix with the consecutive ones property in each column, i.e. each column consists of a single consecutive block of $1$'s (with zeros everywhere else). Is there anything at all I can say about the following optimization problem?\begin{align*} \text{minimize}_{x_{ijk}}\sum_{i}\sum_{j}\sqrt{\sum_{k}c_{k}a_{ik}x_{ijk}} & \,\,\,\,\,\,\,\,\text{subject to}\\ \sum_{j}\sqrt{\sum_{k}c_{k}a_{ik}x_{ijk}} & \leq d_{i}\,\,\forall i\\ \sum_{i}a_{ik}x_{ijk} & =1\,\,\forall j,k\\ x_{ijk} & \geq0 \end{align*}

We assume that $d_i$ and $c_k$ are positive for all $i$ and $k$. Note that the first constraint contains the same entries as in the objective.

Tom Solberg
  • 4k
  • 12
  • 25