NDMI084 - Introduction to Approximation and Randomized Algorithms

This is the practical class for the lecture by doc. Kolman. The practicals take place every odd monday of the semester starting at 15:40 in S7. Information for the Czech practicals can be found here.

I recommend Design of Approximation Algorithms as a study material. Section 1.2 contains a relatively good introduction to linear programming.

Conditions for passing the practicals

Over the course of the semester, three sets of homework will be given out. Thirty out of the sixty possible points will be needed for a pass. You will have at least two weeks to complete each set. Hand in your homework on paper or via email as a PDF.


Third set - Deadline 16.1.

I recommend handing this in before the holidays so you can enjoy them in peace.
Triangle removal - 9 points
You were given a convex polyhedron. Your task is to modify it into a similar-looking convex polyhedron that has no triangular faces. You are only permitted to add new faces of negligible dimensions (when compared to original faces) by truncating vertices. Come up with the best possible approximation algorithm for determining the minimal number of vertices to truncate.
Parallel max-4-cut - 13 points
Create a parallel approximation algorithm for max-4-cut. You have n⁴ processors at your disposal. The goal is to have a deterministic ¾-approximation in O(log n) worst-case time, but some points will be awarded for worse results. HINT: I would start with a randomized algorithm, but there are probably multiple ways to do this.

Second set - Deadline 8.12.

Every task is worth 6 points.
Max k-cut
Given a graph, assign each vertex to one of k partitions such that as many edges as possible connect two vertices of different partitions. Find a deterministic (k-1)/k-approximation algorithm.

Hint: Start with randomized 2-cut. Partial points will be available for a randomized solution.
Ring network routing
Given a cycle of n computers connected in a ring topology network and a list of m messages to be sent from computer s_i to computer t_i (for i in 1,...,m), your task is to decide which direction should each message travel around the ring so that the number of messages using the most frequently used edge is as low as possible. Design a 2-approximation algorithm.
We have already seen that Quicksort runs in O(n log n) expected and O(n^2) worst-case time. Let us try and analyze Quicksort a little more carefully. Find an upper bound on the number of comparisons needed to sort n elements with probability at least 1-1/n.

First set - Deadline 2.11.

Every task is worth 4 points.
What is the probability of getting at least 5 heads in a row in 30 tosses of a fair coin? Provide the method you used to compute the result and make sure the result is accurate to within 0.01 percentage point. HINT: I would not recommend doing this by hand.
Assuming that the Subset sum problem is NP-hard, prove that both Subset sum and Partition problems are NP-complete. Subset sum problem = given a target number and a list of numbers, decide if there exists a subset with sum equal to target Partition problem = given a list of numbers, decide if there exists a way to partition the list of numbers into two groups with equal sums.
In the MAX SAT problem, we are trying to satisfy as many of the clauses as possible. Imagine that we assign a value to each variable independently randomly with 50% probability of True and 50% probability of False. What is this algorithm's approximation ratio? Why?
Suppose you wish to select a uniformly random number from the set {1,2,3,4,5,6,7} but only possess a D6. How could you simulate the desired result? How many rolls of a D6 would you expect to need? Try to get as close as possible to the optimum.
Prove that the Christofides algorithm is not better than a 3/2-approximation. More formally, describe infinitely many graphs such that the ratio between the solution found by Christofides and the optimum solution converges to 3/2 as the graphs get larger.