Assignment 4 Activity Selection

CSC373 
Assignment 4

Instructions
1. Be sure to include your name and student number with your assignment. Typed assignments
are preferred (e.g., PDFs created using LaTeX or Word), especially if your handwriting is
possibly illegible or if you do not have access to a good quality scanner. Please submit a
single PDF on MarkUS at https://markus.teach.cs.toronto.edu/csc373-2019-09.
2. You will receive 20% of the points for any (sub)problem for which you write “I do not know
how to approach this problem.” (you will receive 10% if you leave the question blank and do
not write this or a similar statement). Not applicable to BONUS questions.
3. You may receive partial credit for the work that is clearly on the right track. But if your
answer is largely irrelevant, you will receive 0 points.
Q1 [20 Points] Activity Selection
There are m students in a class, and a set of activities U happening in the class. Each student i is
involved in a subset of activities Si ⊆ U. We are told that for every activity in U, there are exactly
four students involved in that activity.
We need to select some of the students as representatives. Our constraint is that for each activity
in U, at least three of the four students involved in that activity must be selected. However, each
student i already has some workload wi 0. So subject to that constraint, we want to minimize
the total workload of the students selected as representatives.
(a) [5 Points] Write this problem as an integer program with 0-1 variables. Briefly explain what
your variables are, and how an optimal solution to your program represents an optimal solution to
our problem.
(b) [15 Points] Use LP relaxation and rounding to obtain a deterministic 2-approximation algorithm. Explain why your rounded solution is a feasible solution to the integer program and why it
provides 2-approximation.
Q2 [20 Points] Coffee Shop Dilemma
(1, 1) (1, 2) · · · (1, n)
· · ·
(2, 1) (2, 2) · · · (2, n)
.
.
.
.
.
.
· · ·
.
.
.
(m, 1) (m, 2) · · · (m, n)
1
Your friends want to break into the lucrative coffee shop market by opening a new chain called The
Coffee Pot. They have a map of the street corners in a neighbourhood of Toronto (shown above),
and for each (i, j), an estimate pi,j 0 of the profit they can make if they open a shop on corner
(i, j). If they open shops on multiple corners, their profits add up. So ideally, they would like to
open a shop at every corner (“the dream”).
However, if they open a shop on corner (i, j), municipal regulations forbid them from opening shops
on adjacent corners (i−1, j), (i+ 1, j), (i, j −1), and (i, j + 1) (whichever exist). As you can guess,
they would like to select street corners where to open shops in order to maximize their profits!
(a) [5 Points] Consider the following greedy algorithm to try and select street corners. Give
a precise counter-example to show that this greedy algorithm does not always find an optimal
solution. Clearly state your counter-example (values of m, n, and pi,j for 1 6 i 6 m, 1 6 j 6 n),
the solution found by the greedy algorithm, and a different solution with larger profit.
C ← {(i, j) : 1 6 i 6 m, 1 6 j 6 n} # C is the set of every available corner
S ← ∅ # S is the current selection of corners
while C 6= ∅:
pick (i, j) ∈ C with the maximum value of pi,j
# Add (i, j) to the selection and remove it (as well as all corners adjacent to it) from C.
S ← S ∪ {(i, j)}
C ← C \ {(i, j),(i − 1, j),(i + 1, j),(i, j − 1),(i, j + 1)}
return S
(b) [15 Points] Prove that the greedy algorithm from part (a) gives 4-approximation.
[Hint: Let S be the selection returned by the greedy algorithm and let T be an optimal solution.
Show that for all (i, j) ∈ T, either (i, j) ∈ S or there is an adjacent (i
0
, j0
) ∈ S with pi
0
,j0 pi,j .
What does this means for all (i, j) ∈ S and their adjacent corners?]
Q3 [20 Points] Randomized Algorithm
Recall that a 3CNF formula ϕ = C1 ∧ . . . ∧ Cm consists of a conjunction of m clauses, where each
clause is a disjunction of exactly 3 literals. In the standard (unweighted) Exact Max-3-SAT problem, our goal was to maximize the number of clauses that are “satisfied” (i.e. in which at least one
literal is true). Recall that the naive randomized algorithm from class provides 7/8-approximation
for this and can be derandomized.
Now, consider a related problem, Exact Robust-Max-3-SAT, in which a clause is considered “satisfied” when at least two literals are true, and the goal is still to maximize the number of clauses
that are “satisfied”, but under the new definition of clause satisfaction.
(a) [5 Points] Give a randomized 1/2-approximation algorithm for Exact Robust-Max-3-SAT.
Specifically, your algorithm should return a random truth assignment of variables such that the
expected number of clauses “satisfied” is at least m/2. Argue correctness of your algorithm.
(b) [15 Points] Derandomize your algorithm to derive a deterministic algorithm which always
returns a truth assignment of variables “satisfying” at least m/2 clauses. Write pseudocode for
your derandomized algorithm, justify its correctness, and analyze its worst-case running time.
2