# 机器学习代写 | Midterm, CSCI 5525 2021

1. Suppose M and N are two disjoint matchings in a graph. Give an O (|M| + |N)-time algo-rithm to decompose M U N into two disjoint matchings M’ and N’ such that |M’|- |N’| ∈{0,土1}.

2. Let G = (U,W, E) be a bipartite graph. Given a maximum matching M of G, describe a linear-time algorithm to compute a Hall set T∈U.

3. Let G = (U,W, E) be a bipartite graph. A vertex in U∪W is essential if it is covered by all maximum matchings. Suppose M is a maximum matchingin G. Give a linear-time algorithm to find all essential vertices in G.

4. Let D = (V,A;w) be a directed graph with positive edge weight function w. Give an O(|V|(|A|+ |V| log |VI))-time algorithm to find a collection of vertex-disjoint circuits in D whose total edge weight is maximum.

5. Suppose that there are m machines and n jobs. Each job j has a processing time Pij on machine i. A scheduling for them partitions the n jobs into m sequences J1,J2,… , Jm, and assigns Ji (possibly empty) to the machine i for 1 < i≤m. If a job j appears as the k-th job in Ji, it would finish at time which is the sum of the processing time of the first k: jobs in Ji. Give a polynomial-time algorithm to compute a scheduling which minimizes the total finishing times of all jobs.

6. [PhD Session only] Let G = (U, W, E;l) be an edge-weighted bipartite graph with l(e)> 0 for each e∈E. Suppose that the total weight of the edges incident to each vertex in UU W is exactly one.

(a) Show that |U|= |W| and G has a perfect matching. (Hint: Use the Hall’s condition.)

(b) Let n:= |U| and m:= |E|. Give an O (m2)-time algorithm to decompose l into a linear combination of at most m- n + 1 incidence vectors of perfect matchings in G. ( Hint: Use a warm-start to generate all but the first perfect matchings.)