Combinatorial Algorithms
Spring 2015
MP Johnson

Problem Set 3
Due by email, 11:59pm, Thursday, May 20th

You're free to work with a partner, but the solutions you submit must be written "in your own words."
  1. The Hitchcock Problem is a special case of min-cost flow, and a generalization of the assignment problem (i.e., min-cost perfect bipartite matching): given is a weighted bipartite graph with nodes $U \cup V$ and edge costs $c_{uv}$, where each source node $u \in U$ has a supply $s_u$ and each sink node $v \in V$ has a demand $d_v$. The problem is to choose an amount to ship on each edge so that all demands are satisfied, with minimum total cost (there are no capacities on the edges):

    $\min \sum c_{uv}f_{uv}$
    s.t.
    $\sum_v f_{uv} \le s_u \quad \forall u$
    $\sum_u f_{uv} \ge d_v \quad \forall v$
    $f_{uv} \ge 0 \quad\quad \forall (u,v)$

    1. Show that you can, without loss of generality, rewrite the problem turning the first two inequality constraints into equalities (with the addition of some new nodes and edges, but without otherwise changing the formulation's structure).

    2. Show that the problem reduces to min-cost flow, say, to the version of it where you're seeking a min-cost flow of value $f=\sum_v d_v$. (Hint 1: create sink nodes $V$ corresponding to all the nodes of the original graph.) (Hint 2: create source nodes $U$ corresponding to all the arcs in the original graph.) (Hint 3, if you want: see Papadimitriou and Steiglitz, the internet, etc.)

  2. Konig and Egervary (the namesakes of the Hungarian method):
    1. Write down a straightforward LP formulation for unweighted bipartite maximum matching, where the constraint matrix $A$ is the (undirected) node-edge adjacency matrix.

    2. Given a nice property of that constraint matrix and your formulation's right-hand-side, conclude that bfs's of your formulation are integral.

    3. Write down the dual of your formulation. What problem is it solving?

    4. Apply strong duality to your LPs to obtain immediate proof of Konig's Theorem.

    5. Within this problem let lines mean rows and columns. Given a 0-1 matrix, say that a given subset $Z$ of its 0s is independent if no line contains multiple members of $Z$.

      Using Konig's Theorem (hint: what bipartite are you going to use?), prove the Konig-Egervary Theorem: the maximum size of an independent set of 0s (i.e., the maximum such $Z$) equals the minimum number of lines that cover all all 0s.

  3. Recall the primal-dual algorithm for shortest path, which tuns out to be essentially the same as Dijkstra, except that the not-yet-"closed" nodes all have the same price (i.e., estimated distance), equal to the distance of the most recently closed node.

    Recall also the string model of the shortest path problem's dual, where given an undirected graph, we cut a piece of string of length equal to each edge, tie the strings together where they meet at nodes, and, say, attach a marble at each knot.

    We know the maximum distance $s$ and $t$ knots can be pulled apart turns out to be the length of the shortest path. Describe a (very) simple physical procedure you could carry out with the string/marble graph apparatus, which would perform or implement the primal-dual algorithm. Explain what events occurring over the course of this procedure correspond to cycles in the primal-dual algorithm's loop (i.e., the closing of new nodes).