# Questions tagged [duality]

The tag has no usage guidance.

15 questions
Filter by
Sorted by
Tagged with
14 views

### What does the complementary slackness theorem say intuitively/in layman's terms?

In layman's terms: weak duality theorem states that all feasible solutions to the primal LP is less than or equal to all feasible solutions to the dual LP. strong duality theorem states that the ...
1 vote
19 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
166 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, ...
546 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 ...
• 7,534
60 views

• 173
253 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 ...
• 453
136 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 ...
• 453
366 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