Homework 9

Description

Problem 1. (10pts)

The following graph G is an instance of a circulation problem with demands. The edge weights represent capacities and the node weights (in parentheses) represent demands. A negative de-mand implies source.

1. Transform this graph into an instance of max-flow problem.

2. Now, assume that each edge of G has a constraint of lower bound of 1 unit, i.e., one unit must flow along all edges. Find the new instance of max-flow problem that includes the lower bound information. (Find G’ in lecture slides)

Problem 2. (9pts)

Determine if these statements are correct.

1. In a flow network, if the capacity of every edge is odd, then there is a maximum flow in which the flow on each edge is odd. (3pts)

2. The following flow is a maximal flow. (3pts)

Note: The notation a/b describes a units of flow on an edge of capacity b.

c) Given the min-cut, we can find the value of max flow in O(|E|). (3pts)

Problem 3. (11pts)

A company sells k different products, and it maintains a database which stores which customers have bought which products recently. We want to send a survey to a subset of n customers. We will tailor each survey so it is appropriate for the particular customer it is sent to. Here are some guidelines that we want to satisfy:

• The survey sent to a customer will ask questions only about the products this customer has purchased.

• We want to get as much information as possible, but do not want to annoy the customer by asking too many questions. (Otherwise, they will simply not respond.) Based on our knowledge of how many products customer i has purchased, and easily they are annoyed, our marketing people have come up with two bounds 0 ≤ c_i ≤ c^′_i. We will ask the ith customer about at least c_i products they bought, but (to avoid annoying them) at most c^′_i products.

• Again, our marketing people know that we want more information about some products (e.g., new releases) and less about others. To get a balanced amount of information about each product, for the jth product we have two bounds 0 ≤ p_j ≤ p^′_j , and we will ask at least p_j customers about this product and at most p^′_j customers.

The problem is how to assign questions to consumers, so that we get all the information we want to get, and every consumer is being asked a valid number of questions.

Problem 4. (10pts)

Kleinberg and Tardos, Chapter 7, Exercise 7

Problem 5. (practice)

Kleinberg and Tardos, Chapter 7, Exercise 9

2