Questions tagged [duality]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
0answers
14 views

Given a primal LP p, and another LP d, how can i formally prove that d is the dual problem of p?

Given a primal LP p, and another LP d, how can i formally prove that d is the dual problem of p? Specifically, i'm talking about the shortest s-t path: where: And the dual LP:
1
vote
1answer
59 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 ...
2
votes
1answer
128 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 ...
1
vote
1answer
104 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 ...
2
votes
1answer
80 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 ...
2
votes
1answer
358 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 ...
4
votes
1answer
85 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 ...
4
votes
0answers
164 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 ...
4
votes
0answers
113 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 ...
2
votes
1answer
311 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?
10
votes
1answer
4k 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: & \...