What's the complexity class of the algorithm I'm seeking?

Question

I'm trying to write a MATLAB algorithm that will resolve the following problem

For some symmetric, positive semi-definite matrix S

minimize (over vector x)  x'*S*x

             subject to     sum(x)==n
                            x(i) is either 1 or 0 for all i
                            n is an integer < the row/column size of S

I'd asked about this question here. Although no answer there satisfies the problem, some of the responses provide me with leads as to how I might answer the question myself. It's been suggested to me that this problem is NP-Hard, but because I have only a CS101 understanding of complexity classes I'm having trouble understanding this.

How can I tell whether this is the case? If it is NP-Hard, should I just give up on trying to find a solution?

Dunno about how the positive semi-definite part affects things, but there's a fairly straightforward reduction from the NP-complete maximum clique problem to the version of your problem where the matrix just has to be symmetric. — user2357112, Nov 22 '15 at 04:31
Note that if it is NP-Hard, you'd *only* need to give up on finding the optimal solution. There are plenty of ways to find good approximate solutions, which can be practically useful even if they aren't the best solutions. — Nuclearman, Nov 22 '15 at 04:51

Tung Le · Answer 1 · 2015-11-22T04:23:48.720

0

NP-Hard is a way of saying that a problem can not be solvable in polynomial time. So, to give up on this problem, you must prove that your problem can not be solvable in polynomial time. I am really confused about your problem formulation as above since your constraints (1) and (3) basically are the same. In constraint (2), it should be an inequality condition since you want to optimize it, like sum()<=n.

 subject to
      0 <= x(i) <= 1        for all i (1)
      sum(x)==n                       (2) 
      x(i) is either 1 or 0 for all i (3)

If you want to stick with Matlab, Yalmip is one of the options you could consider.

edited Nov 22 '15 at 04:23

answered Nov 22 '15 at 04:14

Tung Le

109
1
3
11

You are right that `0 <= x(i) <= 1 for all i` is redundant. It isn't the same as `x(i) is either 1 or 0 for all i`, though, since the latter bit of code makes it clear that the values must be 0 or 1. – user1205901 - Слава Україні Nov 22 '15 at 04:50
As for (2), it's correct as `==` since I'm not trying to optimize it. I will prespecify `n` as being some integer. What I'm trying to minimize is `x'*S*x`. – user1205901 - Слава Україні Nov 22 '15 at 05:17
If you keep as == in constraint (2), your problem will hardly be solvable in polynomial time. So, this constraint needs to be relaxed to be solvable by using <=. – Tung Le Nov 22 '15 at 05:21

score 0 · Accepted Answer · edited May 23 '17 at 12:23

0

The problem in question is a general quadratic 0-1 problem, and therefore is NP-hard. A source for this assertion is Pardalos & Jha (1992). I learned of this paper from this answer to a related question I raised.

Pardalos, P. M., & Jha, S. (1992). Complexity of uniqueness and local search in quadratic 0–1 programming. Operations Research Letters, 11(2), 119-123.

edited May 23 '17 at 12:23

Community

1
1

answered Dec 07 '15 at 10:42

user1205901 - Слава Україні

927
1
12
26

score 0 · Answer 3 · 2015-12-19T06:10:17.997

When parameterized by n, your problem is W[1]-hard, by reduction from independent set.
That applies even if the entries of S are given in unary.

S = adjacency_matrix + ( number_of_vertices - 1 ) * identity_matrix

By the Gershgorin Circle Theorem, such matrices S are always positive semi-definite.

What's the complexity class of the algorithm I'm seeking?

3 Answers3