Let $n \in \mathbb{N}, [n] = \{1,2,\ldots,n\}$ and consider the following optimization problem:

$$\max \sum_{i \in [n]} \sum_{j \in [n]} x_i \cdot x_j \cdot c_{i,j}$$ $$s.t.~~~~~~~~~~~~~~~~~~~~~~~~~~~~$$ $$\forall q \in Q: ~~~~~\sum_{i \in S_q} x_i \leq 1$$ $$\forall i \in [n]~~~~~~~~~~~~~x_i \geq 0$$ where $S_q \subseteq [n]$ for every $q \in Q$ and $c_{i,j} \in \mathbb{N}$ for every $i,j \in [n]$. Let $m = |Q|$; assume that $m = \log(n)$, that is, the number of variables is exponential in the number of nontrivial constraints. Further, assume that $|S_q| = m^{O(1)}$ for all $q \in Q$.

Question: Under what conditions can we get an $\alpha$-approximation for this problem in time $m^{O(1)}$?

If this was a linear program (LP), I would find the dual problem and try to solve it using the ellipsoid method by constructing a separation oracle. Is there a similar analog for such a (non-linear) program with a large number of variables?

  • $\begingroup$ How could you possibly do time $m^{O(1)} = \log^{O(1)} n$, when just representing the input (or the output) takes space polynomial in $n$? Maybe you are imagining the input is given in some implicit representation? If so you need to say explicitly what it is. Likewise for the output. Also, something else funny: with your assumptions, at most polylog$(n)$ variables occur in constraints, and any variable that doesn't can be set to an arbitrarily large value. So (unless the number of positive $c_{ij}$ is at most polylog $n$), the optimization problem must be unbounded. $\endgroup$
    – Neal Young
    Oct 18, 2023 at 20:20
  • $\begingroup$ ... For it not to be unbounded, it must be that, for every positive $c_{ij}$, both $x_i$ and $x_j$ are one of the polylog$(n)$ variables that occur in a constraint. For that to happen, there must be only polylog$(n)$ positive $c_{ij}$'s. So why not assume that is the case, and that the input encoding explicitly lists only the positive $c_{ij}$'s. Then the input encoding has size polylog$(n) = $ poly$(m)$. So the instance is equivalent to a poly$(m)$-size instance of the same problem without your stated restrictions, and you are asking for a poly-time algorithm for such an instance. $\endgroup$
    – Neal Young
    Oct 18, 2023 at 20:31

1 Answer 1


This is a quadratic program (QP). If the matrix $C$ where $(C)_{i,j} = c_{i,j}$ is positive semi definite, then the problem is convex. It seems that your problem should have non-empty interior, so if it is convex, strong duality holds. Thus you could solve the dual problem using the Ellipsoid method, assuming you have a separation oracle for the dual constraints.

If the problem is not convex then I am not sure what can be done.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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