# Questions tagged [duality]

The tag has no usage guidance.

11 questions
Filter by
Sorted by
Tagged with
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:
65 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 ...
202 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 ...
203 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 ...
103 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 ...
402 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 ...
91 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 ...
184 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 ...
120 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 ...