Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Assignment No 4- CS 538, S2023

Date Due: April 16th, 2023

1.  (i) Prove directly from the primal-dual solution to the Hitchcock problem (trans-shipment problem) that only an empty arc can become inadmissible after modification of the dual variables.  Construct an example in which an arc does in fact become inadmissible.  (10pts)

(ii) Run the algorithms on the following problem: There are 4 warehouses (indexed with i) with supply (3, 4, 2, 1) and 4 clients (indexed with j) with requirements (3, 2, 3, 2). The costs are cij  = 2i−3j+100. (10pts)

2.  Show that in a bipartite graph the maximum matching size is the same as the minimum cover size. A cover is a set S of vertices where every edge in the graph is incident onto a vertex in S .  (15pts)

3.  Detail the proof of correctness (in particular show why compressing the blossom is correct).  Analyze the complexity of the matching algorithm on general graphs.  (10pts)

Is the following statement true or false::  If G = (V,E) is a graph, M a matching and B a blossom, then there is an augmenting path in G w.r.t M iff there is one in G|B where blossom B is compressed into one vertex.  (15pts)

4.  Suppose we generalize the matching requirement in bipartite graphs such that each node has not one but can have at most b edges incident onto it. Given an algorithm for maximum b-matching in bipartite graphs.  (20pts)

5.  (i) Prove the correctness of the  algorithms for weighted bipartite matching  and  analyze the time complexity.  (5pts)

(ii) Show that in the Hungarian method, when weights are integers the dual variables are always half-integral (i.e. multiples of 1/2) (10pts)

(iii) Run the algorithms on the problem in 1(ii) with requirements (1 , 1, 1, 1).  (5pts)