assignment in Algorithms
stikyb
assignment_6_1.pdf
Assignment #6 CS4/531, Fall 2013 Due Date: Monday, Dec. 9, 2013, 3:00 - 4:00 pm.
• UNSUPPORTED SOLUTIONS RECEIVE NO CREDIT.
• Total points: 30
Note: The problems marked 0 points will not be collected nor graded. However, it is very important for you to do these problems as if they were to be graded. (Because similar problems will appear in exams). Detailed solutions to all problems (including 0 point problems) will be provided.
• Guideline for all homework assignments
– HW must be handed-in between 3:00 - 4:00pm Monday, Dec 9, during TA’s office hours.
– Print your name, and UB number on the first page.
– Staple all sheets together. Do not use notebooks and folders.
– The solutions can be hand-written, but must be legible.
– Present the solutions in sequential order. Make sure the problem number is clearly marked, and leave space between problems.
– If you do not follow these guidelines, TA may deduct up to 20% of points.
1. (0 points) In the network shown in Figure 1, s1, s2, s3 are all sources. The supply available at s1 is sup(s1) = 5, at s2 is sup(s2) = 10, at s3 is sup(s3) = 5. The vertices t1, t2, t3 are all sinks. The demand required at t1 is dem(t1) = 5, at t2 is dem(t2) = 10, at t3 is dem(t3) = 5. The capacity of each edge is as indicated.
Determine whether all the requirements can be met simultaneously. (Namely: the capacity constraint is satisfied for all edges; the flow conservation constraint is satisfied for the vertices a, b, c, d; the total flow out of each si (for i = 1, 2, 3) is sup(si); the total flow into each ti (for i = 1, 2, 3) is dem(ti).)
To solve the problem, you need to convert it to an instance of the basic network flow problem, run the Edmonds-Karp algorithm, then answer the question.
1
2
3
1
7
4
s1
4
5
a
7
6
2
3
3
8
9 8
b c
d 8
2
7
s2
s3
t1
t2
t3
Figure 1: The network for Problem 1
2. (8 points) Ad assignment problem.
1
Imagine that you work for Yahoo and are in charge of sending ads to users. You must send ads to users according to the following constraints:
1. Users:
(a) At the given minute, you know that n users u1, . . . , un are visiting Yahoo.
(b) Each user belongs to a number of demographic groups (we will simply call them groups). From user profile information, you know which users belong to which groups.
(c) Each user ui (1 ≤ i ≤ n) specifies that he wants to see at most ci ads per min.
2. Groups:
(a) There are k distinct groups G1, G2, . . . , Gk.
(b) These groups may overlap. For example, G1 might be all residents in Buffalo. G2 might be all people who love pizza.
3. Advertisers:
(a) There are m different advertisers A1, . . . , Am.
(b) Each advertiser Ai specifies a subset Xi ⊆ {G1, . . . Gk} of groups. Ai wants its ads shown only to users who belong to at least one of the groups in the set Xi. (For example if X1 = {G1, G2}, then A1 wants its ads shown to users who are either Buffalo residents or who love pizza).
(c) Each advertiser Ai will pay Yahoo 1/2 cent per ad send to a user, up to Ci ads per min (Ci is a constant specified in the contract between Ai and Yahoo).
Your goal is to maximize the number of ads Yahoo send to users within 1 min, (this will maximize Yahoo’s ad revenue, and hence your pay-check).
Describe how to convert this problem to a max-flow problem. Food for thought: The above description is a general frame work for this kind of problems.
There are many possible variations. Some examples are given below. Think about it, but do not spend too much time. (They will not be collected, nor graded. Some can be hard, some are impossible).
(a) Suppose that we replace the constraint 3 (c) by the following: In the contact between Ai and Yahoo, Yahoo must send AT LEAST Ci ads to users per min. (If this is done, Ai will pay Yahoo $100 per min. Otherwise Ai will sue Yahoo for breach of contract).
Your job: Describe an algorithm to determine if Yahoo can fulfill all contracts.
(b) A user may limit the number of ads he receives as a member of a particular group. (For example, the user u1 may be willing to see 1 ad as a member of group G1, but 10 ads as a member of G2. An advertiser may be willing to pay more for ads to particular groups. (For example, A1 may pay 1/2 cent per ad for users in the group G1, but 2 cents per ad for users in the group G2).
How do you handle these variations in your max-flow model?
(c) The constraint 3 (b) is too weak. It makes much more sense for A1 (a Buffalo pizzeria) to show ads to users who are Buffalo residents and love pizza. Suppose we change the constraint 3 (b) to the following: We must send ad to users who belong to every group in Xi.
Is there a way to model the problem as a max-flow problem?
2
3. (2 × 5 = 10 points). The Graph Coloring (GC) problem is defined as follows. The input is an undirected graph G = (V,E) with n vertices and m edges. A vertex coloring of G is an assignment of colors to the vertices of G so that for any two vertices u, v, if (u, v) is an edge of G, u and v are assigned different colors. The problem is: Given G, determine the smallest integer k such that G has a vertex coloring using k colors. (Note that G can be colored by two colors iff G is bipartite.)
(a) Describe the decision version of the GC problem. (b) Suppose that we have an algorithm A for solving the decision version of the GC problem
with run time T (n,m). Describe an algorithm B for solving the optimization version of the GC problem. Analyze the run time of B (in terms of T (n,m).)
(c) Consider the following Task Scheduling (TS) problem. There are unlimited number of processors at a computing center. There are n tasks T1, T2, . . . , Tn to be processed on these processors. Each task can be processed by any processor in one time slot. When a task Ti is being processed, it needs to access certain files. If two tasks Ti and Tj need to access the same file, then Ti and Tj cannot be processed during the same time slot, due to file access conflicts. The problem is: How to schedule the tasks so that all tasks are processed within minimum number of time slots.
Describe how to convert the TS problem to the GC problem. (d) Describe a polynomial size certificate for this problem. (e) Describe a non-deterministic polynomial time algorithm for solving this problem.
4. (0 points) Answer True or False. You should be able to justify your answer. (X ≤P Y denotes: “X is polynomial time reducible to Y ”.)
(a) If a problem X is in NP and is in P, then P = NP.
(b) If a problem Y is NP-complete and is in P, then P = NP .
(c) Let X and Y be two problems. If X ≤P Y and X is in P, then Y is in P.
(d) Let X and Y be two problems. If X ≤P Y and Y is in P, then X is in P.
(e) To show a problem X is NP-hard, it is enough to find an NP-complete problem Y and prove X ≤P Y .
In the following problems, if you are asked to show a problem Q is NPC, you must show two things:
1. Show Q ∈ NP. You can do this by describing a polynomial time non-deterministic algorithm for solving Q. (Or by describing a polynomial size certificate for Q and a polynomial time verification algorithm for Q.)
2. Show Q is NP-hard. You can show this by picking a known NPC problem R and show R ≤P Q.
If you are asked to show a problem Q is NP-hard, you only need do (2).
5. (6 points) A figure-8 graph of order 2k − 1 is a graph consisting of 2k − 1 vertices and two cycles (each with k vertices) with one common vertex. The graph shown in Figure 2 is a figure-8 graph of 7 vertices.
Consider the following problem: Given an undirected graph G = (V,E) and an odd integer t, decide if G has a figure-8 graph of order t as a subgraph.
Show this problem is NP-complete.
3
Figure 2: The Figure-8 graph with 7 vertices
6. (6 points) Hitting Set Problem. Input: A set S and a collection {S1, §2, . . . , Sm} of subsets of S. (Namely each Si is a subset
of S), and an integer k. Question: Is there a subset X ⊆ S so that |X| ≤ k and, for each Si (1 ≤ i ≤ m), Si and X
have at least one common element? Interpretation: S= the set of UB students. Each Si (1 ≤ i ≤ m) is a student club. We want
to select a committee X so that X consists of at most k students, and each club Si has at least one member in the committee (if a student belongs to more than one club, then he can represent all clubs he belongs to). Is this possible?
Show Hitting Set Problem is NP-hard.
7. (0 points) Hamiltonian Path (HP) Problem. Let G = (V,E) be an undirected graph. A Hamiltonian Path is a path P of G that passes
through every vertex of G exactly once. HP Problem: Given G = (V,E), does G has a HP? Prove HP is NP-hard, by showing HC≤PHP. (Note: HC is the Hamiltonian Cycle problem).
4
