26
Luca, since a year has passed, you probably have researched your own
answer. I'm answering some of your questions here just for the
record. I review some Lagrangian-relaxation algorithms for the
problems you mention, and sketch the connection to learning (in
particular, following expert advice). I don't comment here on SDP
algorithms.
Note that the ...
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 ...
19
Per OP's wish, here's the math.SE answer I link to in my comment above.
Maybe it's worthwhile to talk through where the dual comes from on an example problem. This will take a while, but hopefully the dual won't seem so mysterious when we're done.
Suppose with have a primal problem as follows.
$$
Primal =\begin{Bmatrix}
\max \ \ \ \ 5x_1 ...
19
I think the difficulty is that this wording slightly misleading; as they state more clearly in the Introduction (1.2), "the expected values of the dual variables constitute a feasible dual solution."
For every fixed setting of the dual variables $X$, we obtain some primal solution of value $f(X)$ and a dual solution of value $\frac{e}{e-1}f(X)$. (The dual ...
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 ...
16
A major open problem in mathematical programming is designing a strongly polynomial time linear programming algorithm. A related problem is whether any variant of the simplex algorithm runs in strongly polynomial time. It makes sense to first prove strong polynomial time bounds for variants of simplex applied to problems for which we already know strong ...
16
The ellipsoid method and interior point methods can be extended to solve SDPs as well. You can refer to any standard-texts on SDPs for details. Here's one:
Semidefinite Programming. Vandenberge and Stephen Boyd, 1996.
16
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
I strongly recommend the paper by Bixby, the "father" of CPLEX, that surveys not only on implementing aspects of the (revised) simplex algorithm: Robert E. Bixby, Solving Real-World Linear Programs: A Decade and More of Progress, Operations Research (50) 2002, 3-15.
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
In general it is not true: Consider two dual- to cyclic d-polytopes with n facets each and merge them along a vertex. (This is the dual operation of gluing two polutops). The number of vertices will be like $n^{[d/2]}$ and the spectrual gap will be roughly 1 over this. (You can use d edges to separete the graph into two parts.
I proved 1/poly(n) seperation ...
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
3,9152 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
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
Elaborating on Mike's answer and Vazirani's comment, you get the dual by considering the general form of an optimality proof for the solution to the original problem. Suppose you have a maximization problem given some linear inequalities, and without loss of generality, suppose you're trying to maximize the variable $x$. Given a solution in which $x = B$, ...
7
Weak duality is a property stating that any feasible solution to the dual problem corresponds to an upper bound on any solution to the primal problem. In contrast, strong duality states that the values of the optimal solutions to the primal problem and dual problem are always equal.
Was this helpful enough?
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 ...
Only top voted, non community-wiki answers of a minimum length are eligible
