The last class
Andy Novocin
Daily Challenge
Consider the following heuristic for vertex cover. Construct a DFS tree of the graph, and delete all of the leaves from this tree. What remains must be a vertex cover of the graph. Prove that the size of this cover is at most twice as large as optimal.
Inteview Question (IRL)
What happens when you type http://www.google.com in a web browser address bar and press enter?
You have 45 minutes, go as deep as you want with your explanation.
Math Challenge
Factor the following integer
188198812920607963838697239461650439807
163563379417382700763356422988859715234
665485319060606504743045317388011303396
716199692321205734031879550656996221305
168759307650257059
Practice Tests Available
Real tests can be returned
Save the whales
Go online and do your course evaluations!
Coding Theory Factoid
The previous math challenge still holds
But it is also impossible, the paper was called
Optimal binary one-error-correcting codes of length 10 have 72 codewords
A still available challenge is codes of length 16 each of which are at least 5 apart from the others
The range of possible values is 256-340
Advertisement
My winter and spring courses will be available at prof.ninja
(Statistics II, Discrete Math, Coding Theory and Cryptography, Advanced Web Technologies)
I will keep this course's materials online at the permanent address http://cisc320f14.prof.ninja
Office hours next week
What times are best?
Plan to be around daily from 10-6
We can make a planned day (Wednesday maybe) if wanted.
PA4 Doodle
Sorry for the delay.
ICUP reduction
Reduce 3-SAT to 0-1 Integer Programming
That is this: given \(A\) an \(n \times m\) matrix and \(b\) an \(n \times 1\) vector, find a 0-1 vector (\(m \times 1\)), \(x\) such that \(Ax \geq b\).
In other words, select which columns of \(A\) add to \(b\) if possible.
Hint: (1 minus the number of complements)
Approximations
Much like heuristics but provably close to the answer.
Simple Example
Vertex Cover Approximation
cover = []
While E not empty:
pick (u,v) from E
cover.push(u,v)
delete from E all edges incident to u or v.
How to justify it
The edges which get picked form a matching (share no edges between their incident vertices)
So each of those edges requires at least 1 vertex in ANY cover.
We kept both so we are no more than twice the number of vertices in THE OPTIMAL cover.
ICUP
Devise a graph in which our approximation is always sub-optimal.
Vertex Cover to Independent Set to Clique
Take the rest of the vertices from the smallest vertex cover, is it the largest independent set?
Take the complement graph (only the edges which are not in your graph), is the largest independent set of one the largest clique of the other?
ICUP
Does an approximation for Vertex Cover yield an approximation to Clique?
Proof that poly-time approximation is (sometimes) NOT possible
Knapsack problem: fit maximal valued subset of items into bag with capacity C.
Suppose that you had a polynomial time algorithm which approximates the answer to within a constant range N.
That is, it finds a subset which is valued more than the optimal value - N.
Then just have it approximate a solution where all values are multiplied by N+1
Real life approximations
It is NP-Hard to approximate the shortest vector in a lattice to within a polynomial factor
Sometimes this is enough
If you can make a solution to a derived problem from an approximation
OR if you can prove that no other answer exists that is within the approximation zone (often hard)
Practice Problems
Practice test problems or 9-7 through 9-16 or 9-25 through 9-30