5
$\begingroup$

I am looking for references whether this problem can be doable in polynomial time (or other known approximation results):

Let $f$ a super-additive function ($\forall x,y, f(x+y) \geq f(y)+f(y)$), $$ \min \sum_{i=1}^n f(y_i) $$ under the constraints $$ Ay \geq b $$

To answer to Peter Shor's comment, we are trying to find the vector $y=(y_1,\cdots,y_n)$, $A$ is a $n\times n$ matrix. We suppose that $k$ is a constant.

I am particularly interested in the case where $f$ is a piecewise linear function, not continuous ($\exists (a_1,\cdots,a_k),0<\alpha_1<\cdots<\alpha_k) $, such that $\forall x\in ]a_i,a_{i+1}], f(x) = \alpha_{i+1}x$).

It seems to me that the ellipsoid algorithm could work for those special functions, but I have not been able to find any references, maybe because either this is a sub problem of a known problem? Note that I am trying to solve this for any rational values.

(Note that this is a sub-question of What classes of mathematical programs can be solved exactly or approximately, in polynomial time?)

$\endgroup$
  • $\begingroup$ Are you trying to find the $n$ values of $y_i$ that minimize this? What are the relative sizes of $n$, $k$, and $\dim A$? $\endgroup$ – Peter Shor Jun 19 '13 at 12:46
  • $\begingroup$ @PeterShor, thank you, I have corrected my text accordingly. $\endgroup$ – Gopi Jun 19 '13 at 13:47
  • $\begingroup$ The first thought that comes to mind here is to use the technique of column generation. The idea is to start with just a few possible values of $y_i$, set up the resulting problem as a linear program, and solve it. Then find more values of $y_i$ to add to the permissible set that will lower the minimum, and repeat. It would require some work to fill in the details (if this technique does indeed work), and I don't have the time to work this out. $\endgroup$ – Peter Shor Jun 19 '13 at 15:45
  • $\begingroup$ Are you trying to solve this problem in practice, or are you trying to prove that it can be solved in polynomial time? $\endgroup$ – Peter Shor Jun 19 '13 at 15:55
  • 4
    $\begingroup$ I did not understand what you meant by "not continuous" when you consider the piece-wise linear case. If you do have continuity then isn't your function convex in this case? In that case you are doing convex function minimization subject to convex constraints and the problem should be solvable in polynomial time. $\endgroup$ – Chandra Chekuri Jun 20 '13 at 17:51
7
$\begingroup$

The problem as presented is NP-hard.

Suppose we have $f(y)=0, y\leq 1$ and $f(y) = y, y > 1$. Now if we have the constraints $y_1 + y_2 \geq 2.01$ and $y_i \geq 0$, and we want to minimize $\sum_i f(y_i)$, clearly we should choose one of these $y_i$ to be $1$ and one to be $1.01$.

Now, suppose we have a graph $G$, and we put a constraint like this for every edge. Replace $2.01$ by $2 + \epsilon$ for a sufficiently small $\epsilon$. (You don't even need to do this, because vertex cover has an inapproximability result.) To minimize the objective function, we want to find the minimum number of vertices that hit every edge. This is the minimum vertex cover problem, and it is NP-complete.

The only reason that this isn't exactly your problem is that the matrix $A$ is not square, because the number of variables is the number of vertices in $G$, and the number of equations is the number of edges in $G$. But you can always add dummy vertices that don't participate in the equations to make $A$ square.

Possibly your real problem has more structure so that this NP-completeness proof doesn't apply. Maybe if you told us more about the real problem, it might be solvable in polynomial time.

For convex $f$, this should be solvable in polynomial time ... see Chandra's comment.

$\endgroup$
  • $\begingroup$ Nice result. Indeed my problem has more structure, so I will see another way. I am still looking for references on approximation results though. $\endgroup$ – Gopi Jun 22 '13 at 8:02

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.