CSCI 570 – Spring 2021 – HW 4
Due April 01, by 4AM PST
Note. You are to solve problems 2, 3 and 4 by using the following steps:
1. Describe how to construct a flow network.
2. Make a claim. Something like ”this problem has a feasible solution if and only if the max flow is …”
3. Prove the above claim in both directions
1 Running the Algorithm (15 points)
You are given the following graph G. Each edge is labeled with the capacity of that edge.
a. Find a max-flow in G using the Ford-Fulkerson algorithm. Draw the resid- ual graph Gf corresponding to the max flow. You do not need to show all intermediate steps. (10 pts)
b. Find the max-flow value and a min-cut. (5 pts)
1
2 Trading Currencies (20 points)
A group of traders are leaving Switzerland, and need to convert their Francs into various international currencies. There are n traders t1, t2, . . . , tn and m currencies c1 , c2 , . . . , cm . Trader tk has Fk Francs to convert. For each currency cj, the bank can convert at most Bj Franks to cj. Trader tk is willing to trade as much as Skj of his Francs for currency cj .(For example, a trader with 1000 Francs might be willing to convert up to 200 of his Francs for USD, up to 500 of his Francs for Japanese’s Yen, and up to 200 of his Francs for Euros). Assuming that all traders give their requests to the bank at the same time, design an algorithm that the bank can use to satisfy the requests (if it is possible).
3 Getting Vaccinated (20 points)
After getting vaccinated, students will be able to return to in-person classes next semester. There will be n students, s1, s2, …, sn, return to in-person classes, and there will be k in-person classes. Each in-person class consists of several students and a student can be enrolled in more than one in-person class. We need to select one student from each in-person class and the maximum times a student is selected should be less than m. Design an algorithm that decides if such a selection exists, or not.
4 Visiting Campus (25 points)
USC Admissions Center needs your help in planning paths for Campus tours given to prospective students or interested groups. Let USC campus be modeled as a weighted, directed graph G containing locations V connected by one-way roads E. On a busy day, let k be the number of campus tours that have to be done at the same time. It is required that the paths of campus tours do not use the same roads. Let the tour have k starting locations A = { a1, a2,…, ak } ⊂ V . From the starting locations the groups are taken by a guide on a path through G to some ending location in B = { b1, b2,…, bk } ⊂ V . Your goal is to find a path for each group i from the starting location, ai , to any ending location bj such that no two paths share any edges, and no two groups end in the same location bj.
a. Design an algorithm to find k paths ai → bj that start and end at different vertices and such that they do not share any edges. (15 pts)
b. Modify your algorithm to find k paths ai → bj , that start and end in different locations and such that they share neither vertices nor edges. (10 pts)
2
5 Circulation (20 points)
In the network below, the demand values are shown on vertices (supply value if negative). Lower bounds on flow and edge capacities are shown as (lower bound, capacity) for each edge. Determine if there is a feasible circulation in this graph. You need to show all your steps.
a. Turn the circulation with lower bounds problem into a circulation problem without lower bounds. (8 pts)
b. Turn the circulation with demands problem into the maximum flow problem. (8 pts)
c. Does a feasible circulation exist? Explain your answer. (4 pts)
6 Installing Software (Not Graded)
Suppose that you have just bought a new computer and you want to install soft- ware on that. Specifically, two companies, which you can think of like Microsoft and Apple, are trying to sell their own copy of n different products, like Opera- tion System. Spread Sheet, Web Browser. For each product i, i ∈ {1, 2, . . . , n}, we have
• the price pi ≥ 0 that Microsoft charges and the price p′i ≥ 0 that Apple charges.
• the quality qi ≥ 0 of Microsoft version and the quality qi′ ≥ 0 of Apple version.
For example, Apple may provide a better Web Browser Safari, but Microsoft a better Word Processor. You want to assemble your favorite computer by installing exactly one copy of each of the n products, e.g. you want to buy one operating system, one Web Browser, one Word Processor, etc. However,
3
you don’t want to spend too much money on that. Therefore, your goal is to maximize the quality minus total price.
However, as you may know, the products of different companies may not be compatible. More concretely, for each product pair (i,j), we will suffer a penalty τij ≥ 0 if we install product i of Microsoft and product j of Apple. Note that τij may not be equal to τji just because Apple’s Safari does not work well on Microsoft Windows doesn’t mean that Microsoft’s Edge does not work well in Mac-OS. We assume that products are always compatible internally, which means that there is no penalty for installing two products from the same company. All pairwise penalties will be subtracted from the total quality of the system.
Your task is then to give a polynomial-time algorithm for computing which product i to purchase from which of the two companies (Apple and Microsoft) for all i ∈ {1,2,…,n}, to maximize the total system quality (including the penalties) minus the total price.
4