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,722
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,722
17
votes
Accepted
Intuitively, why is the complementary slackness condition true?
As you have noted, complementary slackness follows immediately from strong duality, i.e., equality of the primal and dual objective functions at an optimum.
Complementarity slackness can be thought of ...
- 1,713
14
votes
Accepted
Why is complementary slackness important?
Complementary slackness is key in designing primal-dual algorithms. The basic idea is:
Start with a feasible dual solution $y$.
Attempt to find primal feasible $x$ such that $(x, y)$ satisfy ...
- 18k
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
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
9
votes
Intuitively, why is the complementary slackness condition true?
I find the geometric interpretation useful. Say we have the primal as $\max c x$ subject to $Ax \le b$ and $x \ge 0$. We know that optimum solutions are vertices of the polytope defined by the ...
- 6,659
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,633
8
votes
Vertices of a polytope
No. Suppose all $a_i$'s are $0$ and all your $b_i$'s are equal; then the polytopes you can get by varying the $b_i$'s are essentially the hypersimplices. But the number of vertices of an $n$-...
- 50.3k
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 ...
- 23.7k
7
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,718
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 ...
- 18k
7
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 ...
- 8,273
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,722
6
votes
Accepted
Is cubic complexity still the state of the art for LP?
It seems that K.M.Anstreicher has improved the result to $O((n^3/\ln n)L)$ in Anstreicher, Kurt M. "Linear programming in O ([n3/ln n] L) operations." SIAM Journal on Optimization 9, no. 4 (1999): 803-...
- 86
6
votes
What are some of the most ingenious linear programs developed for tackling hard combinatorial problems?
The relaxation of Calinescu, Karloff and Rabani for the undirected Multiway Cut problem is one my favorites. Had a big influence on subsequent work.
http://www.sciencedirect.com/science/article/pii/...
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,722
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 ...
- 18k
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,722
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,722
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 ...
- 8,273
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, ...
- 8,273
5
votes
What are some of the most ingenious linear programs developed for tackling hard combinatorial problems?
Some of the linear programs which comes to my mind are
George Dantzig’s linear program for Traveling Salesman Problem. You can find a nice description of the result here.
Flow based Linear program ...
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. ...
- 8,273
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$ ...
- 18k
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
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.3k
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
Only top scored, non community-wiki answers of a minimum length are eligible