24 votes
Accepted

How "hard" is it to maximize a polynomial function subject to linear constraints?

Your problem is NP-hard, even for polynomials of degree 2. The crucial reference is Theodore Motzkin and Ernst Strauss (1965) "Maxima for graphs and a new proof of a theorem of Turan" ...
Gamow's user avatar
  • 5,762
20 votes
Accepted

Is there a counterexample to this work?

Predecessor versions of this paper have been around for more than 15 years. I remember that there were counter-examples to the first versions, then first revisions, counter-examples to the first ...
Gamow's user avatar
  • 5,762
12 votes
Accepted

Checking equivalence of two polytopes

I cannot say for sure if you will consider the following approach as better, but from a complexity-theoretic point of view there is a more efficient solution. The idea is to rephrase your question in ...
Christoph Haase's user avatar
12 votes

Finding the sparsest solution to a system of linear equations

Consider the problem $\text{MAX-LIN}(R)$ of maximizing the number of satisfied linear equations over some ring $R$, which is often NP-hard, for example in the case $R=\mathbb{Z}$ Take an instance of ...
Joe Bebel's user avatar
  • 2,295
9 votes

Proof of $LP$ is in $coNP$ without showing it is in $P$?

Note: all vector inequalities in this reply are to be interpreted pointwise. Given a linear feasibility problem, you can always rewrite it in the following canonical form: given a matrix $A \in \...
Yonatan N's user avatar
  • 1,642
8 votes

Solving linear equations involving min

I assume the generalization you are thinking of is the following: Given value $d$, and values $s_i$ and $r_i$ for $i = 1,2,...,k$, find (if possible) an $\alpha$ such that $$\sum_{i = 1}^k\min(r_i, ...
Mikhail Rudoy's user avatar
8 votes
Accepted

Is there a simplex-like algorithm that can be used with a separation oracle?

I'm not sure if you would consider the algorithms I'll discuss here "Simplex-like" (but see the comment about column generation at the end). If you have a weak separation oracle for a ...
Neal Young's user avatar
  • 9,595
7 votes
Accepted

Is finding an optimal solution to this Knapsack-like problem NP-hard?

NOTE: My original reduction didn't work. Fixed now. Can't subset-sum be reduced to this problem fairly easily? Suppose all the profits $v_i$ are the same, say $v_i = 1$, and all the profits $p_i$ are ...
Peter Shor 's user avatar
7 votes
Accepted

Complexity of finding a consistent hyperplane

Second version, hopefully correct. I claim that solving the feasibility problem $\exists? x: Ax \le b$ reduces in strongly polynomial time to finding a linear separator. Then it's easy to reduce ...
Sasho Nikolov's user avatar
6 votes

Finding the sparsest solution to a system of linear equations

The problem is NP-complete, by reduction from the following problem: Given an $m\times n$ matrix $A$ with integer entries and an integer vector $b$ with $n$ entries, does there exist a 0-1 vector $x$ ...
Gamow's user avatar
  • 5,762
6 votes

Reaching the double exponential upper bound in Fourier-Motzkin elimination

I think this upper bound is tight. As an example, consider the following system \begin{align*} +x_0 & +\frac{1}{2} x_1 +\frac{1}{4} x_2 \le 0 \\ +x_0 & +\frac{1}{2} x_1 +\frac{1}{4} x_2 \le ...
Sasha Kozachinskiy's user avatar
6 votes
Accepted

On complexity of linear programming with quadratic equality/inequality constraints?

A famous result by Motzkin and Straus expresses the $k$-clique problem as the maximization of a quadratic function subject to a system of linear constraints. In particular, they prove: Let $G$ be ...
Gamow's user avatar
  • 5,762
6 votes
Accepted

How is SDP an extension of spectral algorithms?

This is not a precise statement so it's hard to give a precise answer, but I think what is meant is that SDPs are powerful enough to express both linear programs, and problems like "compute the ...
Sasho Nikolov's user avatar
6 votes
Accepted

Complexity of Finding Largest Set of Intersecting Convex Polytopes

Suppose that the dimension $d$ of the Euclidean space is fixed, and that the input consists of $n$ convex polytopes in $\mathbb{R}^d$ that altogether have $p$ facets. Let $h_1,\ldots,h_p$ denote the ...
Gamow's user avatar
  • 5,762
6 votes
Accepted

Minimal number of hyperplanes needed to separate sets of points from one other set

Your problem is NP-complete, even in the following two highly restricted cases: The dimension $d$ is part of the input, and the question is whether you can separate set $B$ from set $G$ by $k=2$ ...
Gamow's user avatar
  • 5,762
6 votes
Accepted

Generate cut $(A,B)$ in edge-colored graph $(V,E_1 \cup E_2)$ such that there are more red than white crossings, i.e $|E_1(A,B)| > |E_2(A,B)|$

Theorem 1. The given problem is NP-hard, by reduction from MAX-CUT. Proof. Call the given problem Positive Discrepancy Cut (PDC). Define weighted PDC to be the generalization where the input is a ...
Neal Young's user avatar
  • 9,595
6 votes
Accepted

Characterization of integral polyhedra

Here's a proof (sketch) that doesn't explicitly use duality. More precisely, it replaces duality by a seemingly weaker (and hopefully easily believable) geometric fact, in Step 3 below. EDIT: But, ...
Neal Young's user avatar
  • 9,595
6 votes
Accepted

Is there an approximate version of the strong duality theorem for linear programming?

A candidate for a variant of the strong duality theorem is: the primal LP has a solution $\mathbf{x^*}$ for which: $$ \mathbf{b^T y'} \cdot (1+\epsilon) \geq \mathbf{c^T x^*} \geq b^T \mathbf{y'}/(1+\...
Neal Young's user avatar
  • 9,595
5 votes

Cases of Linear programming known to be in $NC$?

Fixed dimensional linear programming (for any constant dimension $d$) is known to be in $\mathsf{NC}$; in fact, it can be done work-efficiently (in the same amount of work as the fastest sequential ...
xal's user avatar
  • 429
5 votes

Is there a polynomial time algorithm to determine if the span of a set of matrices contains a permutation matrix?

Theorem. The problem in the post is NP-hard, by reduction from Subset-Sum. Of course it follows that the problem is unlikely to have a poly-time algorithm as requested by op. Here is the intuition. ...
Neal Young's user avatar
  • 9,595
5 votes
Accepted

NP completeness of linear $0-1$ assignment problem

If I understood it well, (1) is also NP-complete, a possible reduction is from SUBSET SUM: Given a set of $m$ positive integers $A = \{a_1, ..., a_m\}$, and a positive integer $B$, is there a subset ...
Marzio De Biasi's user avatar
5 votes

Decide whether a point is a vertex of a polytope?

This answer expands on Chandra's comment, and on my follow up comment. The problem is indeed solvable in polynomial time. More general versions of it are also solvable in polynomial time: $\Theta$ ...
Sasho Nikolov's user avatar
5 votes

Checking equivalence of two polytopes

The fact that the underlying polytope $Ax \le b$ is the same for $P_1$ and $P_2$ does not matter, unless we know something specific about $A$ and $b$. This is because a general polytope is an affine ...
Denis Pankratov's user avatar
5 votes
Accepted

Does an upper bound on the integrality gap imply an approximation algorithm with the same ratio?

See Feige and Jozeph's paper on separation between estimation and approximation.
Chandra Chekuri's user avatar
4 votes

Finding the sparsest solution to a system of linear equations

This problem is hard, in various settings. As stated in the other answers to this question, the problem is NP-complete over the integers. In signal processing, the matrix and the vectors have ...
argentpepper's user avatar
  • 2,281
4 votes

NP completeness of linear $0-1$ assignment problem

It seems that we can reduce Subset Sum to your problem (2). Hence, your problem (2) is NP-complete. Consider the following formulation of Subset Sum. Instance: A multi-set consisting of $n$ ...
Michael Wehar's user avatar
4 votes

Finding the sparsest solution to a system of linear equations

This is called the Sparsest Solution Vector problem, and it is indeed NP-hard.
R B's user avatar
  • 9,428
4 votes
Accepted

Minimum relevant variables in linear system - additive approximation

Unless $P=NP$, there does not exist a polynomial time approximation algorithm that returns solutions of value at most $\text{OPT}+d$. Suppose otherwise, and consider some fixed $d$ for which there ...
Gamow's user avatar
  • 5,762
4 votes
Accepted

Can one efficiently uniformly sample a neighbor of a vertex in the graph of a polytope?

Edit 2: Embarrassingly, there is a two line proof of the $NP$-hardness, if one starts with the right polytope. First, recall the circulation polytope of a graph on the bottom of page 4 of Generating ...
Areawoman's user avatar
  • 1,439

Only top scored, non community-wiki answers of a minimum length are eligible