Undergraduate based. (a) F, (b) F. (c) F, (d) F, (e) T, (f) F.

\(x_{i, j}= 0 \dot\vee x_{j, i} = 0\)

undergraduate, hw description:

Find the longest path in the residual network by inspection. (Note: finding the longest path in a network is NP-complete unless the network is acyclic.)

Labeling Algorithm Page 184

Graduate base, proof. Description:

Gives a proof if the answer is yes or a no.

We would need an arc that goes over $O(n^2)$ many pairs of paths for all the possible path, and we need to firstly show that the previous algorithm 5.40 is not going to work anymore and, if would have no choice to look over almost all the possible path to figure out the optimal path for the pertrubed costs!

Graduate based, proof. Description:

Use the answers from 4.20 to help.

Graduate based, proof. Description:

The state requires that \(s\neq t\) to be true.

By length, the question probably mean the total cost of the directed path.

(a) I think this is just a direct application of the characterization of shortest path conditions, \(d(i, j) = d(i, k) + d(k, j) \; \forall i, j \in N\). (b) I have a feeling that this is a similar proof compare to the Floyd Warshall algorithm as discussed before.

Undergraduate homework question. Description from the assignment sheet:

Order the nodes 1,...,7, and order the arcs with tail node i, A(i), increasing by their head nodes. See next page for the algorithm.

The graph is at the same page. The FIFO Label-Correcting algorithm is exactly the same as Moore Bellman Ford Algorithm. Labels at the end should be: [0, -5, 15, -5, -10]

undergraduated based. Problem description:

Consider the LP formulation of the shortest path problem given on page 94 of the text. Show that shortest path problem LP is unbounded for any feasible network that has a negative cycle.

Undergraduate, description:

Solve the all-pairs shortest path problem using the Floyd-Warshall algorithm to the network given in Fig. 4.15(a). Show the distance matrix for each iteration. To make the matrix more readable, relabel the nodes a,b, ..., f for 1,2,... ,6, and z for node 0.

What the heck is this "z for node 0" under the homework discription, no such node exists in the graph, nor is thre additional nodes for the FW algorithm.

Undergraduate. Proof based. Take note that the converse is definitely not true. But if we assume cycle exists in the predecessor graph, then there has to be a negative cycle cost directed cycle on the original graph.

Key: Page 137, last 10 lines and keep reading. The invariant of the label correcting algorithm is the key.

The reduce costs of all arcs \((i, j)\) on the predecessor graph have to have a reduced cost that is less than zero.\(\forall (j, pred(j)): d(j) \ge d(i) + c_{i, j}\).

Undergraduarte, algorithm based.

Do this one, it's useful for future lectures.

The proof is direct from the fact that a subset of \(\sup\) is smaller gonna be larger than the \(\sup\) of the super set.

Showing something is complete is actally harder than showing something is incomplete, because the trick of looking for an counter example sequence that punch a hole in the space is no useful.

consider the element sequence \(x = (1, 1/2,/3, 1/4, 1/5, 0, \cdots)\) all the way to infinity. Then another sequence that is the truncation of the sequence is in the set \(M\), and it converges to \(x\), but it's not in \(M\). This subspace is incomplete.

This is also not hard to invoke the Cauchy criterion.

Just use \(n, n > \tan(N)\) and exploit the fact that limit of \(\arctan\) is \(\pi/2\). The sequence \(x_n = n\) does the trick. This time we use the Cauchy criterion for the convergence.

yes. It's kinda obvious if you know \(\Vert \cdot\Vert_2\)

A direct application of the holder inequality, which is proved.

homework