\documentclass{article} \input{6854-preamble} \begin{document} \psetnum{5} \date{2004/10/13} \collab{Collaborators: \{\texttt{sarahl,pramook}\}} \begin{pset} \begin{problem} The largest capacity is 15, so four scaling steps will be required. We begin by applying only the highest order bit of the capacity to the graph: \begin{center} \includegraphics[scale=.5]{ps5-1-1.ps} \end{center} The shortest path is $s \to 1 \to 4 \to 6 \to t$ (or $s \to 1 \to 2 \to 4 \to 6 \to t$, which has the same cost, but we arbitrarily choose the former). We augment along this path and compute the residual network: \begin{center} \includegraphics[scale=.5]{ps5-1-2.ps} \end{center} There are no further augmenting paths in the residual network, so we shift in the next bit: \begin{center} \includegraphics[scale=.5]{ps5-1-3.ps} \end{center} The shortest path is $s \to 1 \to 2 \to t$, with capacity 1 and cost 10. We augment along this path: \begin{center} \includegraphics[scale=.5]{ps5-1-4.ps} \end{center} The next shortest path is $s \to 3 \to 4 \to t$, with capacity 1 and cost 20. We augment along this path: \begin{center} \includegraphics[scale=.5]{ps5-1-5.ps} \end{center} The next shortest path is $s \to 3 \to 6 \to t$, with capacity 1 and cost 25. We augment along this path: \begin{center} \includegraphics[scale=.5]{ps5-1-6.ps} \end{center} There are no further augmenting paths. The flow at this stage (scaled up to the original levels) is: \begin{center} \includegraphics[scale=.5]{ps5-1-7.ps} \end{center} \end{problem} \begin{problem} \begin{subproblem} Suppose we are given a flow network and an optimal minimum-cost circulation $F$ on the network, and we wish to change the cost of an edge $e$ in the network by one unit. We begin by computing the residual subgraph of the network. We then calculate a price function using the standard technique of adding a super-source connected to every node with zero-cost edges and computing the distance function and reduced costs. Note that (before the edge cost change) since the minimum-cost flow was optimal, there will be no negative-weight reduced-cost edges in the residual network. If the edge whose cost is being changed has non-zero reduced cost, then the minimum-cost flow does not change due to the cost adjustment: if the cost is increased, we would want to decrease the flow through the edge if possible, but it has zero flow through it. If the cost is decreased by one unit, it is still at most zero since the costs are integral, and so the flow is still an optimal minimum-cost flow on the modified network. If the edge $e$'s reduced cost is zero, then it may have flow through it, and changing the edge cost can affect the minimum-cost flow. If we decrease the cost of $e$, then if it is not at capacity already, we will have a negative reduced-cost edge in the residual network, which can create negative-cost cycles: this means that we need to increase the flow through $e$. If instead we increase the cost of $e$, if the edge has any flow through it, then the reverse edge in the residual network will have negative reduced cost, and can create negative-cost cycles: this means that we need to increase the flow through the reverse edge in the residual network, i.e. decrease the flow through $e$. We can then reoptimize the flow by identifying negative-cost cycles in the residual network and augmenting along them. This is essentially the cycle-canceling algorithm. We know the result will be an optimal minimum-cost maximum flow: the circulation flow value does not change since we are only augmenting along cycles, and the final result will be an optimal minimum-cost flow since all of the negative-weight cycles will have been eliminated. This algorithm runs faster than computing the min-cost flow from scratch, since doing so would require identifying all the negative-cost cycles, while we simply need to consider the cycles that result from modifying the edge $e$, i.e. the cycles that contain $e$. \end{subproblem} \begin{subproblem} We use the standard cost-scaling approach. We begin by generating the network with the highest-order bit of the costs, and performing a min-cost max-flow calculation on it. We then double the cost of each edge, which does not change the flow values in the min-cost max-flow. Next we iterate over the set of edges: for each edge $e$, if the next largest bit of $e$ is set, we adjust the cost of $e$ by 1, and use the algorithm above to recalculate its optimal min-cost flow. This requires $\bigO{m}$ calls to the procedure above. We repeat this procedure for each bit in the costs. With $C$ as the largest cost, there are $\bigO{\log C}$ bits in the representation of the costs, so $\bigO{m \log C}$ calls are required. \end{subproblem} \end{problem} \begin{problem} \begin{subproblem} Suppose we are given a flow network. We can find the minimum-cost flow subject to the constraint that the flow value is at least 90\% of the maximum flow value. Using a max-flow algorithm, we can find the maximum flow; call the flow value $M$. We then create a new flow network. We add a new source vertex $s^*$, and connect it to the old source $s$ with an edge of capacity $M$ and zero cost. We then connect $s$ and $t$ with an edge of capacity $\nicefrac{M}{10}$ and cost zero. We then compute the minimum-cost maximum flow on this network. A flow on the original network can be extracted simply by removing the vertex $s^*$ and the edge from $s$ to $t$. The resulting flow will clearly be at least 90\% of the maximum flow value. The $s$ to $t$ edge allows up to 10\% of the maximum flow to be removed if it decreases the cost of the flow. \end{subproblem} \begin{subproblem} We augment the flow network in much the same way, adding a new source vertex $s^*$ connected to $s$ by a zero-cost edge with capacity $M$. We then add an edge from $s$ to $t$ with capacity $M$ and cost $K$. Then calculating a min-cost max-flow on the resulting network gives a flow that has capacity at most $M$. If it has capacity less than $M$, this means that flow was rerouted through the $s\to t$ edge. Since that edge has cost $K$, this means that passing flow through this edge reduces the flow through the rest of the graph, but it must also reduce the cost by $K$ times as much. So the desired criterion is minimized. \end{subproblem} \end{problem} \begin{problem} \begin{subproblem} Let $P = \cset{\vec{x}}{A\vec{x} \le \vec{b}}$ and $Q = \cset{\vec{x}}{D\vec{x} \le \vec{e}}$ be polyhedra that have empty intersection. So there exists no vector $\vec{n}$ such that $A \vec{n} \le b$ and $D \vec{n} \le e$. Expressing this with a block matrix, there exists no $\vec{n}$ such that \[ \vec{n} \left[ \begin{array}{cc} A & D \\ \end{array} \right] \le \left[ \begin{array}{cc} b & e \\ \end{array} \right] \] Applying Farkas's lemma, since there is no such $\vec{n}$, there must exist a vector $\vec{q} = \left[ \begin{array}{c} y \\ z \\ \end{array} \right]$ that satisfies $\vec{q} \ge 0$ and $\vec{q}\left[ \begin{array}{cc} A & D \\ \end{array} \right] = 0$, i.e. $\vec{y}, \vec{z} \ge \vec{0}$ and $\vec{y} A + \vec{z} D = 0$. It also satisfies \begin{align*} \left[ \begin{array}{cc} b e\\ \end{array} \right] \left[ \begin{array}{ccc} y\\ z\\ \end{array} \right] &\le 0 \\ b\vec{y} + e \vec{z} &< 0 \\ \end{align*} \end{subproblem} \begin{subproblem} Suppose that polyhedra $P$ and $Q$ have empty intersection. Let $\vec{c} = \vec{y} A$. We show by contradiction that for all $x$, $\vec{c}\vec{x} < \vec{c} \vec{w}$ for all $\vec{x} \in P$ and $\vec{w} \in Q$, i.e. that there is a hyperplane separating $P$ and $Q$. Suppose there is no such hyperplane and there exist some $\vec{x}$ and $\vec{w}$ such that \[ \vec{c}\vec{w} \le \vec{c} \vec{x} \] By definition of $\vec{c}$, \[ \vec{y}A\vec{w} \le \vec{y}A\vec{x} \] Since $\vec{x}$ is in $P$, $A \vec{x} < \vec{b}$ \[ \vec{y}A\vec{w} < \vec{y}\vec{b} \] Canceling the $y$, \[ A\vec{w} < \vec{b} \] But by the definition of $P$, this means that $\vec{w}$ is in $P$ as well as $Q$, contradicting that they have an empty intersection. $\nleftrightarrow$ \end{subproblem} \begin{subproblem} We can therefore verify quickly whether the two polyhedra $P$ and $Q$ intersect. If they do intersect, then our proof is a point that is contained by both $P$ and $Q$. Using the definitions $P = \cset{\vec{x}}{A\vec{x} \le \vec{b}}$ and $Q = \cset{\vec{x}}{D\vec{x} \le \vec{e}}$, we can easily verify this. If they do not intersect, then our proof is the $\vec{y}$ and $\vec{z}$ such that $\vec{y}, \vec{z} \ge \vec{0}$, $\vec{y} A + \vec{z} D = 0$, and $b\vec{y} + e \vec{z} < 0$. We can easily verify these claims, and by part a, they suffice to show that the two polyhedra do not intersect. \end{subproblem} \end{problem} \begin{problem} \begin{subproblem} We express the problem of currency trades to maximize the amount of yen obtainable from $D$ dollars as a linear program as follows: Let $x_i$ be the amount of currency traded by client $i$. Then we wish to maximize \[ \sum_{\cset{i}{b_i = \yen}} r_i x_i \] subject to the following constraints: \begin{eqnarray} \label{eq:constge0}\forall i & x_i & \ge 0 \\ \label{eq:constleui}\forall i & x_i & \le u_i \\ \label{eq:constcons}\forall c \neq \$ & \;\;\; \sum_{\cset{i}{b_i = c}} r_i x_i - \sum_{\cset{i}{a_i = c}} x_i &\le 0 \\ \label{eq:constd}& \sum_{\cset{i}{a_i = \$}} x_i &\le D \end{eqnarray} Constraints \ref{eq:constge0} and \ref{eq:constleui} reflect the obvious constraints on how much each client can trade, and constraint \ref{eq:constcons} reflects the constraint that currency cannot be traded unless it is available to be traded. Constraint \ref{eq:constd} ensures that at most $D$ dollars can be traded; we need not consider any currency conversions \emph{back} to dollars and then to other currencies, because these will clearly not be optimal because directed cycles of trades do not make profits. \end{subproblem} \begin{subproblem} We now show that the currency trades resulting from the linear program can be carried out without borrowing any currency. To do so, we view the trades as a ``flow'' network, where each vertex represents a currency, and each directed edge represents a client that is willing to trade the source currency for the destination currency. The flow through an edge $i$ is $x_i$ from the linear program. This ``flow'' network cannot be considered an actual flow network because it violates some of the flow axioms; nonetheless, however, some of the network properties hold. We view the node corresponding to dollars as the source, and the node corresponding to yen as the sink. Then a path of flow between the two corresponds to a sequence of currency trades. The amount of currency traded can be found by successively dividing the amount of flow through each edge on the path by the sequence of exchange rates that converts it back into dollars and taking the minimum. No borrowing is necessary unless there is a cycle in the graph. But a cycle corresponds to a series of trades that returns to a currency it has previously traded, and since these cycles do not make a profit, it would be equally efficient to remove the cycle from the graph. \end{subproblem} \begin{subproblem} Using the same ``flow'' network representation as above, we can identify all paths that lead from dollars to yen, and we can find the amount of currency traded on this path by dividing by the successive exchange rates. To ensure that the resulting set of trades produces only dollars and yen, we eliminate all trades that are not on dollars-yen paths. For each edge on a dollars-yen path, we also reduce the amount of flow through that edge to the minimum required for the dollars-yen traded sequence. This gives an optimal solution that produces the maximum amount of yen and only yen and dollars. \end{subproblem} \end{problem} \end{pset} \end{document}