Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CSOR W4246–Fall, 2021

Homework 4 Theoretical (105 points)

Homework Instructions.

1. For all algorithms that you are asked to “give” or “design”, you should

• Describe your algorithm clearly in English.

• Give pseudocode.

• Argue correctness, even if you don’t give an entirely formal proof.

• Give the best upper bound that you can for the running time.

You are also encouraged to analyze the space required by your algorithm but we will not remove marks if you don’t, unless the problem explicitly asks you to analyze space complexity.

2. If you give a DP algorithm, you should follow the instructions in hw2-theoretical. 3. If you give a reduction, you should do so as we did in class, that is

(a)  Give the inputs to the two problems.

(b)  Describe in English the reduction transformation and argue that it requires polynomial

time.  (You do not need to give pseudocode.)

(c)  Prove carefully equivalence of the original and the reduced instances.

4. You should submit your assignment as a pdf ﬁle on Gradescope. Other ﬁle formats will not be graded, and will automatically receive a score of 0.

5. I recommend you type your solutions using LaTeX. For every assignment, you will earn 5 extra credit points if you type your solutions using LaTeX or other software that prints equations and algorithms neatly.  If you do not type your solutions, make sure that your hand-writing is very clear and that your scan is high quality.

6. You  should  not  use  any  external  resources  for this  homework.   Failure to follow this instruction might have a negative impact on your performance in the second exam and interviews.  For the same reason, you should avoid collaborating with your classmates unless you have thought through the problems on your own for a long time and are unable to make any further progress. I also encourage you to work on all the recommended exercises.

7. You should write up the solutions  entirely  on  your  own.   Collaboration is limited to discussion of ideas only and you should adhere to the department’s academic honesty policy (see the course syllabus). Similarity between your solutions and solutions of your classmates or solutions posted online will result in receiving a 0 in this assignment and possibly further disciplinary actions. You should list your collaborators on your write-up.

Homework Problems

1.  (12 points) Stingy  SAT is the following problem.

On input a SAT formula φ, return a truth assignment that satisﬁes φ and minimizes the number of variables that are set to 1, or no if φ is unsatisﬁable.

Give a polynomial time algorithm for Stingy  SAT, or prove that no such algorithm exists unless P = NP .

2.  (25 points)

Suppose you had a polynomial-time algorithm A for the decision version of the maximum independent set problem IS(D). That is, on input a graph G = (V, E) and an integer k , A answers yes if and only if G has an independent set of size at least k, and A runs in worst-case polynomial time.

Design a polynomial-time algorithm that takes as input a graph G and an integer k, and returns an independent set of size at least k if one exists in G, or no otherwise.

3.  (30 points) A large store has m customers and n products and maintains an m × n matrix A such that Aij  = 1 if customer i has purchased product j; otherwise, Aij  = 0.

Two customers are called orthogonal if they did not purchase any products in common. Your task is to help the store determine a maximum subset of orthogonal customers.

Give a polynomial-time algorithm for this problem or prove that no such algorithm exists unless P = NP .

4.  (38 points) Formulate linear or integer programs for the following optimization problems. (Full-credit will be given to LP solutions, when they are possible.)

(a)  (10 points) Min-cost  flow:  Given a ﬂow network with capacities ce  and costs ae  on

every edge e, and supplies si on every vertex i, ﬁnd a feasible ﬂow f : E → R＋—that is, a ﬂow satisfying edge capacity constraints and node supplies—that minimizes the total cost of the ﬂow.

(b)  (14 points) The  assignment  problem: There are n persons and n jobs that have to be

matched on a one-to-one basis.  There is a given set A of ordered pairs (i, j), where a pair (i, j) indicates that person i can be matched with job j. For every pair (i, j) ∈ A, there is a value aij  for matching person i with job j.  Our goal is to assign persons to jobs so as to maximize the total value of the assignment.

(c)  (14 points) Exact-3SAT: Given a formula φ with n variables and m clauses where each clause consists of exactly three distinct literals, is the formula satisﬁable?

RECOMMENDED exercises:  do NOT return, they will not be graded.)

1.  (Using reductions to prove NP-completeness)

(a) A  clique  in an undirected graph  G  =  (V, E) is a subset  S of vertices such that  all

possible edges between the vertices in S appear in E.  Computing the maximum clique in a network (or the number of cliques of at least a certain size) is useful in analyzing social networks, where cliques corresponds to groups of people who all know each other. State the decision version of the above maximization problem and show that it is NP- complete. Hint:  reduction from Independent  Set .

(b) We say that G is a subgraph of H if, by deleting certain vertices and edges of H we

obtain a graph that is, up to renaming of the vertices, identical to G.

The following problem has applications, e.g., in pattern discovery in databases and in analyzing the structure of social networks.

Subgraph  Isomorphism:  Given two undirected graphs G and H, determine whether G is a subgraph of H and if so, return the corresponding mapping of vertices in G to vertices in H .

Show that Subgraph  Isomorphism is NP-complete.

(c)  Similarly, consider the following problem.

Dense  Subgraph: Given a graph G and two integers a and b, ﬁnd a set of a vertices of G such that there are at least b edges between them.

Show that Dense  Subgraph is NP-complete.

2. You are asked to assist in the following crisis event.

Due to large scale ﬂooding, there is a set of n injured people distributed across a region that need to be rushed to hospitals. There are k hospitals in the region, and each of the n people needs to be brought to a hospital that is within a half-hour’s driving time of their current location (so diﬀerent people will have diﬀerent options for hospitals, depending on where they are right now). However you cannot overload any single hospital; instead, every hospital must receive at most [n/k1 people.

Give an eﬃcient algorithm for this problem.

3.  Suppose you are given n cities and a set of non-negative distances dij  between pairs of cities.

(a)  Give an O(n2 2n ) dynamic programming algorithm to solve this instance of TSP; that

is, compute the cost of the optimal tour and output the actual optimal tour.

(b) What are the space requirements of your algorithm?

Hint:  Let V = {1, . . . , n} be  the set of cities.  Consider progressively larger subsets  of cities; for every subset S of cities including city 1 and at least one  other city,  compute the shortest path that starts at city 1, visits all cities in S and ends up in city j, for every j ∈ S .