Questions tagged [duality]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
1 answer

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 ...
MR_'s user avatar
  • 1,564
1 vote
1 answer

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 ...
Rohit Pandey's user avatar
1 vote
1 answer

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, ...
Sam Winnick's user avatar
4 votes
2 answers

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 ...
Nathaniel's user avatar
  • 12.5k
0 votes
0 answers

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 $...
Jolis's user avatar
  • 1
2 votes
1 answer

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 ...
hengxin's user avatar
  • 9,501
2 votes
1 answer

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 ...
Erel Segal-Halevi's user avatar
1 vote
1 answer

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 ...
m.raynal's user avatar
  • 319
4 votes
1 answer

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 ...
Stephane Rolland's user avatar
2 votes
1 answer

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 ...
Belgi's user avatar
  • 267
4 votes
1 answer

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 ...
Elisha's user avatar
  • 173
4 votes
0 answers

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 ...
user3280193's user avatar
4 votes
0 answers

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 ...
user3280193's user avatar
2 votes
1 answer

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?
xiamx's user avatar
  • 211
11 votes
1 answer

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: & \...
Kaveh's user avatar
  • 22.2k