We have recently covered linear programming and I am comfortable with the weak and strong duality theorems. However, I don't understand what the applications of duality are that are specific to TCS. Mike Spivey's blog post gives some interesting examples of some nice properties of duality but I was wondering if there are algorithmic advances, for example, that come from understanding duality or anything more CS related.
$\begingroup$
$\endgroup$
2
-
$\begingroup$ It would be useful to make precise which duality you have in mind. This term covers many topics in mathematics, as you can see on this list of dualities. $\endgroup$– J.-E. PinOct 27, 2013 at 9:45
-
1$\begingroup$ @J.-E.Pin I think the first sentence makes it perfectly clear he means linear programming duality $\endgroup$– Sasho NikolovOct 27, 2013 at 15:16
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
4
Yup. Everything follows from duality. (I am only half joking). A partial list:
Boosting
The Hard-Core Lemma
Online Learning
The ability to actually solve LPs efficiently
A large fraction of approximation algorithms results.
Much more
To develop algorithms, you often need a constructive or algorithmic version of the duality theorem (which is essentially equivalent to Von-Neumman's min-max theorem in game theory -- the applications in game theory are also huge). This is essentially what the multiplicative weights algorithm is. See Arora/Hazan/Kale for the best survey on this topic: http://www.satyenkale.com/papers/mw-survey.pdf
answered Oct 15, 2013 at 13:43
-
$\begingroup$ Thank you. We may have had a non-typical course but the approximation algorithms we covered didn't seem to require a knowledge of duality and nor did the description of the simplex algorithm. $\endgroup$– user15587Oct 15, 2013 at 14:01
-
1$\begingroup$ The simplex algorithm simultaniously finds a primal and dual solution for the LP it is solving. For applications of LP duality to approximation algorithms, check out Vijay Vazirani's book on approximation algorithms: cc.gatech.edu/fac/Vijay.Vazirani/book.pdf In particular, Part II is largely devoted to this topic. $\endgroup$ Oct 15, 2013 at 19:12
-
1$\begingroup$ Also, chapter 7 of Williamson-Shmoys: designofapproxalgs.com $\endgroup$ Oct 15, 2013 at 19:30
-
1$\begingroup$ since it's very closely related to primal-dual for approximating NP-complete problems, maybe OP will be interested in primal-dual for designing competitive online algorithms: openu.ac.il/Personal_sites/niv-buchbinder/download/… $\endgroup$ Oct 15, 2013 at 23:55
$\begingroup$
$\endgroup$
1
Perhaps the most famous application of duality has been the max-flow min-cut theorem (introduced in Ford & Fulkerson's landmark paper "Maximal Flow Through a Network"). The theorem states, formally, that the optimal solution for the (primal) integer linear program for finding the maximum flow is equal to the same optimal solution for the dual program to find a minimum cut.
The wikipedia page provides a good summary of this concept; http://en.wikipedia.org/wiki/Max-flow_min-cut_theorem
Moreover, this special case of LP duality has been previously studied in a graph-theoretic context, in the form of Menger's Theorem and Konig's Theorem. Menger's Theorem characterizes the number of edge-disjoint paths between vertices $x,y \in V$, and Konig's Theorem states the equivalence between optimal solutions for maximum matching and minimum vertex cover on bipartite graphs (one can find a nice reduction to flows).
-
1$\begingroup$ Menger's theorem and Konig's theorem both significantly predate maxflow-mincut, so "gives rise to" is a bit inaccurate. $\endgroup$– JeffεOct 23, 2013 at 0:20