• 6.5210/18.415: Advanced Algorithms
  • PSets
  • Calendar
  • Materials
  • Information
  • Duality

    David Karger

    Last Time


    Checking feasibility of a given solution is easy. Motivating question: How to certify optimality of a given solution?

    Want: Find a lower bound on \(v^*:=\min \set{c^Tx \mid Ax=b, x \ge 0}\).

    Important observation (and a sanity check): The dual of the dual LP gives the primal LP.

    A simple corollary of weak duality and the above observation: If \(P\) is the primal LP and \(D\) is the dual LP then either

    Strong Duality

    Weak duality described below is just a tip of an iceberg. Strong duality (key theorem of LP): If \(P\) and \(D\) feasible then \(v^*=w^*\).
    “Proof” by picture:

    Formal proof:

    Claim: There exists \(x^*\) such that \(Ax^*=b\).

    Claim: We have that \(b^Ty^*=c^Tx^*\).

    Claim: It is the case that \(x^* \ge 0\).

    (Formalizes the intuition that barriers have to push ball not pull it.)

    Interesting corollary (of strong duality): For LPs, finding a solution that is merely feasible is algorithmically equivalent to finding a solution that is optimal.

    Rules for Taking Duals

    Some observations:

    Insights on Specific Problems via LP Duality

    Shortest Paths Problem

    Maximum Flow Problem

    Complementary Slackness

    Duality leads to another idea: complementary slackness:

    Apply CS to Max-flow Duality

    Minimum Cost Circulation Problem