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"
...
- 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 ...
- 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 ...
- 371
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 ...
- 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 \...
- 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, ...
- 2,758
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 ...
- 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 ...
- 24.3k
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 ...
- 18.1k
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$ ...
- 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 ...
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 ...
- 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 ...
- 18.1k
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 ...
- 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$ ...
- 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 ...
- 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, ...
- 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+\...
- 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 ...
- 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. ...
- 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 ...
- 22.6k
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$ ...
- 18.1k
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 ...
- 377
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.
- 6,979
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 ...
- 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$ ...
- 5,065
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.
- 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 ...
- 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 ...
- 1,439
Only top scored, non community-wiki answers of a minimum length are eligible