Questions tagged [duality]
The duality tag has no usage guidance.
15
questions
1
vote
1
answer
105
views
Minimize bottleneck in flow network
Let $G=(V,E)$ be a flow network with two vertices $s,t$ also each edge has its capacity equal to $\infty$. Our goal is to transfer a flow of size $C$ from $s$ to $t$ so that minimize an edge that has ...
- 1,564
1
vote
1
answer
108
views
Dual of a graph where the faces are unclear
To get the dual of a planar graph, each of the faces becomes a vertex. And then, two vertices in the dual graph are connected if they share a common face. My question is about planar graphs that have ...
- 305
1
vote
1
answer
439
views
What's an example of a planar graph with two embeddings whose geometric duals are nonisomorphic?
How to prove that the dual of the dual of a connected planar graph $G$ is isomorphic to $G$?
In the post linked above, the user "plop" gives a great response where they claim, in particular, ...
- 11
4
votes
2
answers
1k
views
How to prove that the dual of the dual of a connected planar graph $G$ is isomorphic to $G$?
I find in many references the fact that if $G$ is a connected planar graph, then for any embedding, $G^{**} \cong G$. However, all those references either say that this fact is trivial, or give the ...
- 12.5k
0
votes
0
answers
64
views
How can I show a problem is in the intersection of np and co-np using duality and Farkas-lemma?
Currently, I have a hard time to find out the solution to this problem:
Given a matrix $A \in Z^{m \times n}$, $b \in Z^m$, $c \in R^n$ and $\lambda \in R$. Is there $x \in R^n$ with $Ax \leq b$ and $...
- 1
2
votes
1
answer
153
views
What is the intuition behind the way of reading off a dual optimal solution from simplex primal tabular in CLRS?
Section 29.4 "Duality" of CLRS (3rd Edition) describes the way of reading off an optimal dual solution from the last slack form of the primal as follows:
Suppose that the last slack form of the ...
- 9,501
2
votes
1
answer
995
views
Using LP to prove the max matching - min cover theorem
Konig's theorem says that, in a bipartite graph, the size of the maximum matching equals the size of the minimum vertex cover. This theorem has several proofs; I would like to know if the following ...
- 5,720
1
vote
1
answer
1k
views
What is a min-max theorem in graph theory?
I'm currently studying a paper which uses extensively the term 'min-max theorems' in graph theory, and claims to present a tool allowing to generalize these ...
- 319
4
votes
1
answer
166
views
What is a not-well-founded cotree?
I'm reading the paper "Dual of substitution is Redecoration".
And I'm struggling with understanding the usage of the word "not-well-founded cotrees".
what is a cotree compared to a tree ? I suspect ...
- 391
2
votes
1
answer
608
views
Comparing dual of a canonical primal program - Directly and by dual of the standard program
I have it as a homework question to compare dual programs in the following way:
Take a canonical program and write its dual
Take the same canonical program, write it as a standard program, take the ...
- 267
4
votes
1
answer
246
views
Finding a minimal width strip which encloses a set of points in the plane
Problem: Consider a set of $n$ points in the plane, how could we find a strip of minimal vertical distance that contains all points?
Definitions: A strip is defined by two parallel lines and the ...
- 173
4
votes
0
answers
274
views
Intuitive self-contained proof of Farkas' Lemma
I've been studying the proof of Farkas' Lemma, and given my rather fuzzy memory of Linear Algebra, am having some trouble with it. One version of Farkas' lemma states:
For any convex cone generated ...
- 463
4
votes
0
answers
145
views
Showing a linear program is infeasible or finding a feasible solution
I'm aware that for any given maximize/minimize LP problem, if its dual is unbounded then the primary is infeasible and vice versa. But what if there is no maximize/minimize objective function? For ...
- 463
2
votes
1
answer
426
views
What's the dual problem of stable matching?
So the dual problem of max-flow is min-cut. What's the dual problem of stable matching?
- 211
11
votes
1
answer
5k
views
Short and slick proof of the strong duality theorem for linear programming
Consider the linear programs
\begin{array}{|ccc|}
\hline
Primal: & A\vec{x} \leq \vec{b} \hspace{.5cm} &
\max \vec{c}^T\vec{x} \\
\hline
\end{array}
\begin{array}{|ccc|}
\hline
Dual: & \...
- 22.2k