CSOR W4246 Homework 4 Theoretical
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 file on Gradescope. Other file 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 satisfies φ and minimizes the number of variables that are set to 1, or no if φ is unsatisfiable.
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 flow network with capacities ce and costs ae on
every edge e, and supplies si on every vertex i, find a feasible flow f : E → R＋—that is, a flow satisfying edge capacity constraints and node supplies—that minimizes the total cost of the flow.
(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 satisfiable?
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, find 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 flooding, 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 different people will have different 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 efficient 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 .
2021-12-08