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?
What functions are easy to optimize?
optimization;approximation