Instructions
CSC373 Fall’20 Assignment 4: Mathematical Monarch Due Date: December 7, 2020, 11:59pm ET
1. 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. Either way, you need to submit a single PDF named “hwk4.pdf” on MarkUS at https: //markus.teach.cs.toronto.edu/csc373-2020-09
2. You will receive 20% of the points for a (sub)question when you leave it blank (or cross off any written solution) and write “I do not know how to approach this problem.” If you leave it blank but do not write this or a similar statement, you will receive 10%. This does not apply to any bonus (sub)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.
Preface:
You’re the monarch of a state. You were elected as the monarch not because of the family you were born into, but because you always offer the most ingenious mathematical solutions to the everyday problems that the citizens bring to you. Today, four citizens have come to you seeking advice. Let’s hope you can live up to their expectations!
Q1 [20 Points] Communications
A communication engineer in your realm is facing the following problem. There are n communica- tion towers arranged in a circle: that is, tower i connected to tower i+1 for i ∈ {1,…,n−1}, and tower n connected to tower 1. Two towers being “connected” means there are two cables between them, one for carrying communication traffic in each direction. Thus, there are 2n cables in total.
Every second, the central communication planning system receives a set of requests E. Each request k is given by a triplet (ik,jk,ck), which indicates that ck bytes of data must be sent from tower ik to tower jk; here, ck is a positive real number and ik, jk ∈ {1, . . . , n} with ik ̸= jk. This request can be fulfilled by routing the data either in the clockwise direction or in the anticlockwise direction; for example, if there are n = 5 towers and a request requires routing data from tower 2 to tower 4, then wecansenditeitherviatheroute2→3→4orviatheroute2→1→5→4. Theloadoneachca- ble e, denoted Le, is the total amount of data sent across the cable. The overall load is L = maxe Le.
The engineer needs your help designing an algorithm which decides the direction (clockwise / anticlockwise) in which each request should be routed to minimize the overall load.
(a) [5 Points] Write a binary integer linear program which solves this problem exactly. Clearly indicate the meaning of your variables.
(b) [15 Points] Design an efficient 2-approximation algorithm which relaxes the ILP from part (a) to an LP and rounds its optimal solution.
1
[Hint: Even though the decision corresponding to each request k can be modeled as a single binary variable, you might find it more convenient to model it using two binary variables xk and yk.]
Q2 [20 Points] Task Scheduling
Congratulations! Your realm now has a brand new factory, which has n workers and m machines. There are l tasks which must be performed each day in the factory. Each task i must be performed by a specific worker wi on a specific machine mi and this takes a specific amount of time pi.
Given all this data, the factory owner needs to “schedule” the tasks, i.e., assign a start time si ≥ 0 to each task i. Then, each task i will be performed by worker wi on machine mi during the interval [si, si + pi). The only constraint is that no worker can ever work on multiple tasks simultaneously and no machine can ever be used for multiple tasks simultaneously. It is OK for a worker or a machine to be idle between tasks.
The goal is to minimize the overall finish time T, i.e., the time by which all tasks finish. The factory owner, not being as mathematically astute as you, comes to you for advice. You begin by analyzing the following simple greedy algorithm:
Algorithm 1: Task Scheduling
while there still exist unscheduled tasks do
For each unscheduled task i, compute the earliest time si at which it can start, i.e., the
earliest time at which both worker wi and machine mi become available Let i∗ be the unscheduled task with the smallest si∗ (break ties arbitrarily) Schedule task i∗ to start at time si∗
1 2
3 4 5
(b) [5 Points] Briefly argue that the schedule produced by this algorithm has the following property: if worker j is idle at time t, then for every task i yet to be performed by the worker (i.e. with wi = j and si > t), the required machine mi must be occupied for another task i′ (i.e. there must exist i′ such that mi′ = mi and t ∈ [si′ , si′ + ti′ )). In other words, a worker is never idle if she could be working on a yet-to-be-done task.
(c) [10 Points] Use part (b) to prove that this algorithm achieves a 2-approximation. [Hint: It might be helpful to relate four quantities:
• T (the overall finish time of the greedy schedule),
• T∗ (the minimum possible overall finish time of any schedule),
• Wmax = maxj Wj, where Wj is the total processing time of all jobs i with wi = j, • Mmax = maxk Mk, where Mk is the total processing time of all jobs i with mi = k.
One way to relate these quantities is to focus on a task i that finishes last in the schedule produced by the greedy algorithm and relate the time spent by worker wi up to the start time of i to the above quantities. Note that T = si + pi.]
2
end
(a) [5 Points] Briefly argue that this algorithm produces a feasible schedule meeting the constraints.
Q3 [20 Points] Toll Booths
Congratulations! Your realm now has roads. The road network can be represented as an undirected graph G = (V, E) with edges in E representing the roads and nodes in V referred to as junctions. The urban planner wants to build toll booths at the fewest possible junctions such that at least one of the two ends of each road has a toll booth. Upon hearing the problem, you instantly smile: this is the (unweighted) minimum vertex cover problem.
Tapping into your infinite wisdom, you tell the planner that this problem is NP-complete, but you know a simple 2-approximation algorithm. The planner pushes back: Can’t you do any better? You begin to think: in the worst case, 2-approximation is known to be the best possible assuming a widely believed conjecture (“unique games conjecture”). But what if our graph G has a nice structure? Then it hits you: your graph G is planar and, by a popular theorem, every planar graph has a 4-coloring (i.e. a function c : V → {0, 1, 2, 3} such that c(u) ̸= c(v) for all (u, v) ∈ E).
Suppose you are given a 4-coloring c of G. For t ∈ {0, 1, 2, 3}, define Vt to be the set of vertices v with c(v) = t. Without loss of generality, assume |V3| ≥ |V2| ≥ |V1| ≥ |V0|. Your job is to use this 4-coloring to find a better vertex cover of G. Consider the ILP for minimum vertex cover:
min v∈V xv
xu + xv ≥ 1, ∀(u, v) ∈ E xu ∈ {0,1},∀v ∈ V
It is known that the LP relaxation of this ILP has the following property: it has an optimal solution x∗ in which x∗ ∈ {0, 1 , 1} for each v ∈ V . Suppose such an optimal solution x∗ is also given to you.
v2
Given x∗ and c, you define S = {v ∈ V : x∗ = 1 ∨ (x∗ = 1 ∧ v ∈/ V )}.
vv23 (a) [10 Points] Argue that S is indeed a vertex cover of G.
(b) [10 Points] Prove that the algorithm achieves a 3/2-approximation (i.e. |S| will be at most 3/2 times the size of the smallest vertex cover).
Q4 [20 Points] CNF?
An upstanding citizen from your realm, Shah, comes to you with the following problem, but refuses to say where this problem comes from. You don’t like this very much as you’ve grown fond of hearing the stories, but being a good monarch, you still help him out.
Suppose, he says, you are given a CNF formula φ consisting of clauses C1,…,Cm over variables x1, . . . , xn. Your goal is to find an assignment of variables satisfying the maximum number of clauses (MAX-SAT). For each clause Cj, let Pj denote the set of indices i such that Cj contains the literal xi and Nj denote the set of indices i such that Cj contains the literal x ̄i.
(a) [5 Points] Fill in the blanks in the following ILP for this problem:
maximize
subject to for all j ∈ [m]
yi,zj ∈ {0,1} for all i ∈ {1,…,n},j ∈ {1,…,m} 3
(b)[7Points]Supposeyouaregivenafunctionf:[0,1]→Rsuchthat1−4−y ≤f(y)≤4y−1 for all y ∈ [0, 1]. Consider the following approximation algorithm for this problem.
Algorithm A:
1. Solve the LP relaxation of the above ILP. Let the optimal solution be (y∗,z∗).
2. Construct an assignment by independently setting each xi to TRUE with probability f(yi∗).
Show that for each clause Cj , the probability that Cj is not satisfied is at most 4−zj∗ . (c) [8 Points] Use part (b) to show that A is a 4/3-approximation algorithm.
[Hint: You can assume without proof that the function g(z) = 1 − 4−z is a concave function on [0, 1], and hence, satisfies g(λ) ≥ λ · g(1) for all λ ∈ [0, 1].]
4