1
$\begingroup$

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.

$\endgroup$
  • $\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. Pin Oct 27 '13 at 9:45
  • $\begingroup$ @J.-E.Pin I think the first sentence makes it perfectly clear he means linear programming duality $\endgroup$ – Sasho Nikolov Oct 27 '13 at 15:16
11
$\begingroup$

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

$\endgroup$
  • $\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$ – Anush Oct 15 '13 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$ – Aaron Roth Oct 15 '13 at 19:12
  • 1
    $\begingroup$ Also, chapter 7 of Williamson-Shmoys: designofapproxalgs.com $\endgroup$ – Sasho Nikolov Oct 15 '13 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$ – Sasho Nikolov Oct 15 '13 at 23:55
4
$\begingroup$

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).

$\endgroup$
  • 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 '13 at 0:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.