24
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"
Canadian Journal of Mathematics 17, pp 533-540
Motzkin and Strauss consider an undirected graph $G=(V,E)$
with vertex set $V=\{1,2,\ldots,n\}$.
They show that ...
22
In some technical sense you are asking whether $P = NP \cap coNP$. Suppose that $L \in NP \cap coNP$, thus there exists poly-time $F$ and $G$ so that $x \in L$ iff $\exists y: F(x,y)$ and $x \not\in L$ iff $\exists y: G(x,y)$. This can be recast as a minmax characterization by
$f_x(y) = 1$ if $F(x,y)$ and $f_x(y) = 0$ otherwise; $g_x(y) = 0$ if $G(x,y)$ ...
20
The current fastest algorithm is actually linear in the length of the integer linear program for every fixed value of $n$. In his PhD thesis, Lokshtanov (2009) nicely summarizes the results by Lenstra (1983), Kannan (1987), and Frank & Tardos (1987) by the following theorem.
Integer Linear Programming can be solved using $O(n^{2.5n+o(n)} \cdot L)$
...
20
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 revisions, second revisions, new counter-examples, further revisions, further counter-examples, and so on.
It would be much better, if the authors were able to ...
18
A typical problem is MaxCut: output a cut in a graph that (approximately) maximizes the number of edges cut. Goemans and Williamson showed an SDP approximates the value of MaxCut to within a factor at least 0.878. Recently, Chan, Lee, Raghavendra, and Steurer showed that for a natural linear encoding of the MaxCut problem, all polynomial size LPs achieve ...
17
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 as a combinatorial optimality condition, where a zero duality gap (equality of the primal and dual objective functions) can be thought of as a numerical ...
14
Seymour and Thomas showed a min-max characterization of treewidth. Yet, tree width is NP-hard. This however is not quite the kind of characterization you are asking for, because the dual function $g$ is not a polynomial time computable function of a short certificate. This is most likely unavoidable for NP complete problems, because otherwise we would have ...
14
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 complementary slackness.
If step 2. succeeded we are done. Otherwise an obstruction to finding $x$ gives a way to modify $y$ so that the dual objective function value ...
13
Parity games, Mean-payoff games, Discounted games, and Simple Stochastic games fall within this category.
All of them are infinite two-player zero-sum games played on graphs, where players control vertices and choose where a token should go next. All have equilibria in memoryless positional strategies, meaning that each player chooses an edge at each choice ...
12
For many combinatorial optimization problems (for instance Max-Cut), semidefinite programming yields much stronger relaxations than the LP relaxation of IP formulations. This allows the design of approximation algorithms, and of exact algorithms which are more efficient than their linear counterparts due to the better quality of the bounds. Examples can be ...
12
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 the first-order theory of the rationals with addition and order. You have that $P_1$ is included in $P_2$ if and only if
\begin{align*}
\Phi :=
\forall \vec{x}....
12
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 this problem, $Ax=b$ where $A$ is a $n\times m$ matrix. Let $k=m+1$. Construct a new linear system $\tilde{A}\tilde{x} = \tilde{b}$, where $\tilde{A}$ is a $kn ...
10
Yup. Everything follows from duality. (I am only half joking).
A partial list:
Boosting
The Hard-Core Lemma
Online Learning
The ability to actually solve LPs efficiently
A large fraction of approximation algorithms results.
Much more
To develop algorithms, you often need a constructive or algorithmic version of the duality theorem (which is ...
9
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 \mathbb{R}^{m \times n}$ and vector $b \in \mathbb{R}^m$, does there exist an $x \geq \vec{0}$ such that $Ax \leq b$?
Farkas' lemma states that when a system of ...
8
The answer is yes, and in fact one can even reduce to the decision problem of linear inequalities feasibility!
We are as input given a LP instance P:
$\max c^Tx\ \text{s.t.}\ Ax \leq b\ ;\ x\geq 0$.
We furthermore have access to an oracle that given a system of inequalities $S=\{Bz \leq d\}$ returns yes/no, whether the system is feasible.
The reduction ...
answered Jan 29 '14 at 12:41
Kristoffer Arnsfelt Hansen
4,0152 gold badges23 silver badges34 bronze badges
8
This answer is for your "somewhat related question":
In the following recent paper, Klee-Minty cubes were used explicitly to show that there exists a pivoting rule for the simplex method (not one of the standard ones, like Dantzig's pivoting rule analysed by Disser and Skutella) for which it is PSPACE-complete to decide whether a variable enters the basis ...
8
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 constraints. Each such vertex is defined by the intersection of $n$ linearly independent hyperplanes defined by the constraints. When is a vertex solution $x^*$ ...
8
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$-dimensional hypersimplex can be any binomial coefficient $\binom{n}{k}$. In particular choosing $k=n/2$ gives an exponential number of extreme points.
7
The linear program for computing a correlated equilibrium in a game has size that is polynomial in the size of the game matrix: i.e. exponential in the number of players. The scheduling game that you describe is an $n$ player game, so the linear program will not be polynomially sized. However, it is a compactly represented game, so you can in principle use ...
7
Not exactly what you're looking for, but Dinur and Safra, in their celebrated paper on the hardness of vertex cover, prove that the following promise problem is NP-hard for every fixed $r,\epsilon > 0$ (using the PCP theorem and Raz's parallel repetition theorem).
Instance: A graph $G$ whose vertex set is composed of $m$ sets $V_1,\ldots,V_m$ of size $r$,...
7
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 proportional to the weights, so
$p_i = \beta w_i$ with $\beta < 1$.
Now, if there's a set of weights $S$ such that $\sum_{i\in S} w_i = W$, you can get a ...
7
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, s_i\alpha) = d$$
Consider the expression $\min(r_i, s_i\alpha)$. This expression is sometimes equal to $r_i$ and sometimes equal to $s_i\alpha$, with a ...
7
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 linear programming to the feasibility problem.
Let us first reduce the strict feasibility problem $\exists? x: Ax < b$ to finding a linear separator. Towards ...
6
We have developed a user-friendly browser-based system to input and solve 2-player strategic-form and extensive-form games:
http://www.gametheoryexplorer.org/ (GTE)
Currently, we support:
finding all equilibria via polyhedral vertex enumeration (which works on the strategic-form representation, which is converted to in the case of extensive-form games; ...
6
The standard reference is probably Hans Mittelmann's page. Note, however, that the number of simplex iterations performed will depend on the pivoting rule and how the code deals with degeneracy.
6
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-812.. I have not read this paper, but I hope that this answer will help you in some extent.
6
I think $S_n$ can be written in terms of inequalities in the obvious way. Let
$$
Q_n = \{(x, y): x = \sum_{i = 0}^{n-1}{2^i y_i}, \forall i: 0 \leq y_i \leq 1\}.
$$
I claim that $Q_n = S_n$. First, obviously all $(x, y) \in S_n$ are also in $Q_n$, so $S_n \subseteq Q_n$. Second, fix a point $(x^*, y^*) \in Q_n$. Consider the probability distribution over $\{...
6
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/S0022000099916872
6
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$ with $Ax=b$?
For every coordinate $x_i$ of vector $x$,
introduce $100(n+m)$ new equations $x_i+y_{i,k}=0$ with $k=1,\ldots,100(n+m)$, and
introduce $100(...
Only top voted, non community-wiki answers of a minimum length are eligible
