AA Final Assignment (70 marks in total)
Mingyu Guo June 1, 2020
1 Problem 1 (10 marks)
The following statement regarding linear programming is known to be correct:
An LP is either • infeasible
• unbounded
• or has an optimal objective value that is a specific value in [0, +∞)
In a linear program, we only allow =,≤,≥ in the constraints. Suppose we modify the definition of linear programs by also allowing < and > in the constraints. After this modification, is the above statement still correct? Please show your proof.
2 Problem 2 (10 marks)
Consider a bin packing problem where all item sizes are greater than 1/3. Design an algorithm that solves this problem. You have to provide a formal proof to show that your algorithm produces the correct result.
3 Problem 3 (15 marks)
You are running a sandwich shop. You have m different sandwich ingredients. m is a constant. Your existing menu has n types of sandwiches. n is the problem size which may be quite large.
Here is a specific example with m = 3 and n = 4. Your ingredients include egg, tomato, lettuce. Your menu includes:
• Egg Lettuce sandwich
• Egg only sandwich (for muscle builder)
• Tomato with Fried Egg sandwich (Chinese style)
1
• Tomato Lettuce sandwich (vegetarian)
Due to COVID-19, you want to minimize the menu options (to save training cost for new employees). You want to ensure that all ingredients are still being used by at least one type of sandwich. For the above example, the optimal solution involves two types of sandwiches (egg only sandwich and Tomato lettuce sandwich – these two types are enough to cover all three ingredients).
Let f be the number of times the most popular ingredient appears in the original menu. In the above example, f = 3 (Egg appeared three times). Design a f−approximation algorithm. Prove that your solution is indeed a f −approximation.
4 Problem 4 (10 marks)
A conventional dice can be denoted by {1, 2, 3, 4, 5, 6}. It contains six faces, with face values 1 to 6.
A generalized dice has six faces. The face values are still integers between 1 and 6, but we allow duplicates. For example {2, 2, 4, 4, 4, 4} is a valid generalized dice. The total face value of this example dice is 2+2+4+4+4+4 = 20. (The total face value of a conventional dice is 21.)
Given two dices A and B, if we roll both dices many times and A’s result is higher than B’s result with higher frequency, then we say A is a better dice.
5
• •
Problem 1 (5 marks): Is the following statement correct? Provide proof. If A has a higher total face value than B, then A is a better dice.
Problem 2 (5 marks): Is the following statement correct? Provide proof. If A is better than B, B is better than C, then we have A is better than
C.
Problem 5 (10 marks)
A binary sequence is a sequence of 0s and 1s. Here are two example binary sequences with 10 digits each:
s1 = 0100101110
s2 = 0110100110
The distance between s1 and s2 is the number of digits that differ. Here, the distance d(s1, s2) = 2.
Given n binary sequences s1, s2, . . . , sn, all with length n, you are asked to find a sequence t with length n that minimizes the maximum distance between t and any si. That is, you need to find t that minimizes the following:
max d(si,t) 1≤i≤n
2
We define si[j] to be the j-th digit of si. The j-th digit is called “universal” if we have s1[j] = s2[j] = … = sn[j]. Let k be the number of “non-universal” digits.
Design a fixed parameter algorithm for the above problem, where the fixed parameter is k. That is, you are asked to design an algorithm with complexity O(2k poly(n)).
6 Problem 6 (15 marks)
Please work on ONLY ONE of the following tasks.
• Optional Task 1 (15 marks): Read the article “The Solution of the Four- Color-Map Problem” by Kenneth Appel and Wolfgang Haken. (This paper is posted on Canvas.) Use one page to summarize the four-color-map problem, its challenges, and how computers assist its proof.
• Optional Task 2 (15 marks): We went through quite a number of proofs throughout the semester. Among the proofs that we discussed, is there a proof (or a single step of a proof) that can be carried out in computer- assisted style? Please write a short essay on this (1/2 page to 1 page). E.g., you may talk about which proof can be computer assisted and what is the high-level approach. You may also talk about which proof cannot be computer assisted given today’s computing tools.
3