Say I have variables $w_1, \dots w_n, h_1, \dots h_m \in \mathbb R$, constants $W, H$, functions $f_1, \dots f_k : \mathbb R\times\mathbb R\to\mathbb R$ from some family $F$ and for each function $f_i$, a pair of intervals $x_i \subseteq [1, n]$, $y_i \subseteq [1, m]$. All quantities $\geq 0$.

I want to find the $w_i$ and $h_i$ to minimize $\sum f_i \Big(\sum _{j\in x_i} w_j, \sum _{j\in y_i} h_j \Big)$ with constraints $\sum w_i = W$ and $\sum h_i = H$. Approximations are perfectly fine.

Informally, this is a grid with column widths $w_i$ and row heights $h_i$ and cells that may span multiple rows and columns, that have costs $f_i$.

My question is, for what families $F$ does this problem have reasonably efficient solutions? The set of affine functions should work. What about step functions? Piecewise linear? Smooth monotonic? Smooth functions in general?

  • 1
    $\begingroup$ Maybe this would be more suitable for Mathematics $\endgroup$ – dtech Jan 26 '14 at 18:37
  • 3
    $\begingroup$ Also note the convexity of the functions. Convex functions are always easier to optimize. $\endgroup$ – Tolga Birdal Jan 26 '14 at 19:16
  • $\begingroup$ @dtech, why? It's efficiency of algorithms I'm asking about. $\endgroup$ – Karolis Juodelė Jan 26 '14 at 19:34
  • $\begingroup$ @KarolisJuodelė: Because you can often make the argument that optima are at vertices of polyhedra, or that you can alter the solution along a line and stay feasible etc. $\endgroup$ – einpoklum Dec 18 '16 at 17:09

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.