Week 8 (Strong Exponential Time Hypothesis, Approximation Algorithms)

Question 1

What is Big O notation?

Answer 1

f(n) = O(g(n)) if ∃ M>0 & n0 ∈ N such that ∀ n >= n0 we have f(n) <= M.g(n)

Question 2

What is Little o notation?

Answer 2

f(n) = o(g(n)) if lim n-> infinity f(n) / g(n) = 0

Question 3

How do we select a lower bound for NP-Hard problems? Give an example.

Answer 3

We pick a well studied problem which hasn’t been improved in a while and assume it is the optimum e.g SAT

Question 4

What is the infimum of a set?

Answer 4

Infimum of a set S is the greatest number that is <= all elements of S

Question 5

What is the exponential time hypothesis?

Answer 5

δ3 > 0

Question 6

What is the proof for the infimum of SAT?
(Proof of the exponential time hypothesis)

Answer 6

Let Sq = {c : q-SAT can be solved in 2^(c.n).(N+M)^O(1)}
δq = infimum of q

0 ∉ Sq as it implies ∃(M+N)^O(1) time algorithm for q-SAT which implies P=NP

Question 7

What is the consequence of ETH?

Answer 7

3-SAT cannot be solved in 2^o(n) . (N+M)^O(1)

Question 8

What is the proof for the consequence of ETH?

Answer 8

Suppose that 3-SAT can be solved in 2^o(n) . (N+M)^O(1) time
- 3-SAT can be solved in 2^cn . (N+M)^O(1) ∀c>0
- If g(n) = o(n) then CN > g(n) ∀n>=n0
- This implies that S3=(0,1] which has the infimum of 0 => Contradiction

Question 9

What is the Sparsification Lemma?

Answer 9

3-SAT cannot be solved in 2^o(N+M) . (N+M)^O(1) time. This gives us a tight lower bound

Question 10

What can we conclude about P != NP from ETH?

Answer 10

By assuming ETH, since 3-SAT cannot be solved in 2^o(n) . (N+M)^O(1) time then it cannot be solved in poly(N,M) time

Question 11

What does ETH imply about the Independent set?

Answer 11

Since 3-SAT cannot be solved in 2^o(n) . (N+M)^O(1) time then independent set cannot be solved in 3-SAT cannot be solved in 2^o(n/3).(n)^O(1) time. This does not rule out other algorithms such as 3-SAT cannot be solved in 2^o(2n/3).(n)^O(1) time

Question 12

What does ETH say about the minimum vertex cover problem?

Answer 12

Assuming ETH, the minimum vertex cover problem cannot be solved in 2^o(n).(n)^O(1) time. This also tells us that the parameterised k-vertex-cover problem also cannot be solved in 2^o(n).(n)^O(1) time since k<=n-1

Question 13

What is the Strong Exponential Time Hypothesis?

Answer 13

(lim q->infinity δq) = 1

Question 14

What is the proof for the Strong Exponential Time Hypothesis?

Answer 14

Suppose 3-SAT can be solved in 1.99^M.poly(N,M)
- ∀q >= 3, 1.99^M . poly(N,M)
- c ∈ Sq where 2^C = 1.99, c = log2 1.99
- inf(Sq) <= C
- Sq < log2 1.99 < 1 => Contradiction

Question 15

What is the consequence of SETH?

Answer 15

SAT cannot be solved in (2-∈)^N . (N+M)^O(1) time, ∀ ∈>0.

Question 16

What does SETH say about ETH?

Answer 16

If SETH is true, then ETH is also true

Question 17

Why do we use approximately correct algorithms?

Answer 17

Since NP-Hard problems cannot be correct and polytime, we instead find an algorithm that is approximately correct

Question 18

What is c-approximation?

Answer 18

c-approximation for a minimisation algorithm is a solution which costs <= c times the optimal solution

Question 19

What is (1/c)-approximation?

Answer 19

(1/c)-approximation for a maximisation problem is a solution which costs >= (1/c) times the optimal

Question 20

What is the 2-approximation algorithm for vertex cover set?

Answer 20

Matching = set of edges that have no vertex in common
Maximal matching = adding any edge causes it to not be matching

Find a maximal set M of pairwise disjoint edges:
- For each edge ei, see if ei can be added to M (checked in n^O(1) time)
- Return the set S which contains both end-points of each edge in M

If OPT is a vertex cover of minimum size and S is also a vertex cover then |S| >= |OPT|

Since |M| = |S|/2, OPT >= |S|/2

2. |OPT| >= |S| >= |OPT|

Question 21

What is the Integer Program for minimum vertex cover?

Answer 21

min v∈V xv such that for each edge u-w ∈ E we have xu + xw >= 1 where xv ∈ {0,1} for each v ∈ V

Number of variables is |V| and constraints is |E|

Min vertex cover is NP-Hard, so solving integer program is NP-Hard where input size is number of variables plus constraints.

Question 22

What is the running time for linear programs?

Answer 22

Linear programs can be solved in time which is polynomial in the number of variables plus the number of constraints

Question 23

What is the Linear program for minimum vertex cover?

Answer 23

min v∈V xv such that for each edge u-w ∈ E we have xu + xw >= 1 where xv ∈ [0,1] for each v ∈ V

Question 24

How do we round the Linear Program for minimum vertex cover?

Answer 24

Size of minimum vertex cover is OPT IP, OPT LP <= OPT IP
Round OPT LP and round to get OPT rounded LP
- If xv >= 1/2, then set xv = 1
- Else, set xv = 0

OPT rounded LP is still a solution and is <= 2.OPT LP

=> OPT rounded LP <= 2.OPT LP <= 2.OPT IP

Question 25

What is the (1/2)-approximation algorithm for Max Cut problem?

Answer 25

Start with any partition X and V\X - If there is a vertex v ∈ X which has strictly more neighbours in X than in V\X, move v to V\X - If there is a vertex v ∈ X which has strictly more neighbours in V\X than in X, move v to X The strict comparison ensures there is an end result. O(n^2) time to find if a vertex can be switched with O(M) = O(n^2) switches possible. Total running time: O(n^2) . M For each vertex, it has >= half its neighbours on the other side, so there are at least (m/2) edges in the cut which gives >= 1/2 . |E|

Question 26

What is the Max Cut problem?

Answer 26

Given an undirected graph G=(V,E) on v vertices and m edges, find a set X ⊆ V which maximises the number of edges with one endpoint in X and another in V\X

Question 27

What is the k-Centre problem?

Answer 27

Given a set V of n points with a distance function dist: V x V -> R^>=0. Find a set X ⊆ V of size k which minimises max v ∈ V (min x ∈ X dist(v,x)), where dist satisfies the triangle inequality.

Question 28

What is the triangle inequality?

Answer 28

For any triangle, the sum of the lengths of any two sides must be greater than or equal to the length of the remaining side

Question 29

What is the greedy algorithm for the k-Centre problem?

Answer 29

- Start with picking any vertex in X - Keep picking the point v which max(min x ∈ X dist(u,x)) Running time O(n^2). At each step, the next location computes and compares (n-i).i distances <= n^2