cs170_sp21_hw09-sol

HOMEWORK > cs170_sp21_hw09-sol

University of California, Berkeley COMPSCI 170 CS 170 HW 9 Due 2021-04-06, at 10:00 pm 1 Study Group List the names and SIDs of the members in your study group. If you have no collaborators, write \none". 2 Flow vs LP You play a middleman in a market of n suppliers and m purchasers. The i-th supplier can supply up to s[i] products, ...[Show More]

University of California, Berkeley
COMPSCI 170
CS 170 HW 9

Due 2021-04-06, at 10:00 pm

1 Study Group

List the names and SIDs of the members in your study group. If you have no collaborators, write \none".

2 Flow vs LP

You play a middleman in a market of n suppliers and m purchasers. The i-th supplier can supply up to s[i] products, and the j-th purchaser would like to buy up to b[j] products.

However, due to legislation, supplier i can only sell to a purchaser j if they are situated at most 1000 miles apart. Assume that you’re given a list L of all the pairs (i; j) such that supplier i is within 1000 miles of purchaser j. Given n; m; s[1::n]; b[1::m]; L as input, your job is to compute the maximum number of products that can be sold. The run-time of your algorithm must be polynomial in n and m.

For part (a) and (b), assume the product is divisible, that is, it’s OK to sell a fraction of a product.

(a) Show how to solve this problem, using a network flow algorithm as a subroutine. Describe

the graph and explain why the output from the network flow algorithm gives a valid solution to this problem.

(b) Formulate this as a linear program. Explain why this correctly solves the problem, and

the LP can be solved in polynomial time.

(c) Now let’s assume you cannot sell a fraction of a product. In other words, the number of

products sold by each supplier to each purchaser must be an integer. Which formulation would be better, network flow or linear programming? Explain your answer.

Solution:

(a) Algorithm: It is similar to the standard matching to flow reduction. We create a bipartite

graph with n + m + 2 nodes. Label two of the nodes as a \source" and a \sink." Label n

nodes as suppliers, and m nodes as purchasers. Now, we will create the following edges: Create an edge from the source to supplier i with capacity s[i].

For each pair (i; j) in L, create an edge from supplier i to purchaser j with infinite

capacity.

Create an edge from purchaser j to the sink with capacity b[j]. We then plug this

graph into our network flow solver, and take the size of the max flow as the number of dollars we can make.