University of Southern California CSCI 570 hw6_solution

Document Content and Description Below

CSCI 570 - Summer 2017 - HW 6 Due June 23, 2017 1. At a dinner party, there are n families a1; a2; :::; an and m tables b1; b2; :::; bm. The ith family ai has gi members and the jth table bj has hj... seats. Everyone is interested in making new friends and the dinner party planner wants to seat people such that no two members of the same family are seated in the same table. Design an algorithm that decides if there exists a seating assignment such that everyone is seated and no two members of the same family are seated at the same table. Construct the following network G=(V,E). For every family introduce a vertex and for every table introduce a vertex. Let ai denote the vertex corresponding to the ith family and let bj denote the vertex corresponding to the jth table. From every family vertex ai to every table vertex bj, add an edge (ai; bj) of capacity 1. Add two more vertices s and t. To every family vertex ai add an edge (s; ai) of capacity gi. From every table vertex bj add an edge (bj; t) of capacity hj. Claim: There exists a valid seating if and only if the value of max flow from s to t in the above network equals g1 + g2 + ::: + gn. Proof of Claim: Assume there exists a valid seating, that is a seating where every one is seated and no two members in a family are seated at a table. We construct a flow f to the network as follows. If a member of the ith family is seated at the jth table in the seating assignment, then assign a flow of 1 to the edge (ai; bj). Else assign a flow of 0 to the edge (ai; bj). The edge (s; ai) is assigned a flow equaling the number of members in the ith family that are seated (which since the seating is valid equals gi). Likewise the edge (bj; t) is assigned a flow equaling the number of seats taken in the table bj (which since the seating is valid is at most hj). Clearly the assignment is valid since by construction the capacity and conservation constrains are satisfied. Further, the value of the flow equals g1 + g2 + ::: + gn. Conversely, assume that the value of the max s-t flow equals g1+g2+:::+gn. Since the capacities are integers, by the correctness of the Ford-Fulkerson algorithm, there exists a max flow (call f) such that the flow assigned [Show More]

Last updated: 1 year ago

Preview 1 out of 6 pages