$(10$ points$)$ This problem concerns running time optimizations to the Hungarian algorithm for computing minimum$-$

cost perfect bipartite matchings. Recall the $O(m{n}^2)$ running time analysis from lecture: there are at most $n$

augmentation steps, at most $n$ price update steps between two augmentation steps, and each iteration can be

implemented in $O(m)$ time.

$($a$)$ By a phase, we mean a maximal sequence of price update iterations $($between two augmentation iterations$).$

The naive implementation in lecture regrows the search tree from scratch after each price update in a phase,

spending $O(m)$ time on this for each of up to $n$ iterations. Show how to reuse work from previous iterations

so that the total amount of work done searching for good paths, in total over all iterations in the phase, is

only $O(m).$

$($b$)$ The other non$-$trivial work in a price update phase is computing the value of $($the minimum magnitude by

which the prices can be updated without violating any of the invariants$).$ This is easy to do in $O(m)$ time

per iteration. Explain how to maintain a heap data structure so that the total time spent computing $$ over

all iterations in the phase is only $O(mlogn).$ Be sure to explain what heap operations you perform while

growing the search tree and when executing a price update.

$[$This yields an $O(mnlogn)$ time implementation of the Hungarian algorithm.$]$

$(10$ points$)$ We used low$-$stretch trees to approximate APSP on general graphs. We explore this connection

further via the $k-$point$-$facility problem: Given a graph $G=(V,E)$ with positive edge lengths and $kin{Z}_{?}0.$

Define $d_G(u,v)$ to be the length of the shortest path between $u$ and $v$ in $G$ according to these edge$-$lengths. For

a set CsubeV, define

$d_G(v,C)$:$=mi{n}_{\text{c}\text{i}\text{n}\text{C}}{d}_G(v,C)$

The $k-$point$-$facility problem asks you to find a set CsubeV with $|C|=k$ to minimize ${}_G(C)$:$={\displaystyle \underset{\text{v}\text{i}\text{n}\text{V}}{\overset{?}{}}}{d}_G(v,C).$

$($a$)$ Design a poly$(k,n)$ time algorithm to solve the $k-$point$-$facility problem on an edge$-$weighted path of $n$

vertices.

$($b$)$ Given an algorithm to solve $k-$point$-$facility optimally on trees, show that the algorithm that samples a tree

$T$ from $($random$)$ low$-$stretch tree distribution with stretch $,$ solves $k-$point$-$facility on $T$ to get $C_T,$ and

outputs this set $C_T,$ ensures that the expected cost $E_T[{}_G(C_T)]*OPT.$

$($c$)$ Show that if you perform $L$:$=O(\frac{logn}{lon})$ independent runs of the above algorithm to get sets $C_1,C_2,$cdots,$C_L,$

and return the set with the least ${}_G(C_i)$ value from among these $($call it $C^{**}),$ then $.$

OPT

$($d$)$ Show that the expected weight of a low$-$stretch tree is at most $O()$ times the MST$.$

$($e$)$ Extend your algorithm from $($a$)$ to solve $k-$point$-$facility on an edge$-$weighted tree.

$($Hint: first solve it on a binary tree. Then show how to reduce the problem to general trees$)$

give solution in detail by proof each and every step