DM865 - Heuristics and Approximation Algorithms

Sheet 1: Exercises for Friday, February 2

  1. a) Write down an LP-formulation of the unweighted Vertex Cover problem.

    b) Write down the dual of the LP from a).

    c) Which combinatorial problem does the dual correspond to?

Sheet 2: Exercises for Monday, February 5

  1. Although the unweighted Vertex Cover problem is NP-hard for general graphs, there are graph classes that allow for efficient algorithms.
    Design an algorithm that finds a minimum cardinality vertex cover of a tree in linear time.

  2. a) Assume that you have an algorithm for finding a minimum cardinality vertex cover in a graph.
    Explain how you can use the algorithm for finding a maximum cardinality independent set.

    b) Does this mean that you can use an approximation algorithm for unweighted Vertex Cover, like the ones in Sections 1.3 and 1.4, for approximating a maximum cardinality independent set?
    (Hint: What approximation factor could you obtain?)

Sheet 3: Exercises for Tuesday, February 6

  1. Consider the primal-dual algorithm for the unweighted Vertex Cover problem.

    a) What does the algorithm do?

    b) Write down the same algorithm without explicitly using the LP-formulation of the problem.

    c) Give an example showing that the algorithm has an approximation factor of at least 2.

  2. Recall that, for Vertex Cover, the algorithms of Sections 1.3 and 1.4 are 2-approximation algorithms.
    Give an example showing that the greedy algorithm of Section 1.6 is not a 2-approximation algorithm, even for unweighted Vertex Cover.

  3. Give an instance of the Set Cover problem proving that the approximation ratio of the greedy algorithm is at least $H_n$ (i.e., the lower bound of $H_n$ is tight).
    Hint: What does the upper bound of $H_g$ tell us about such an example? (Recall that $g$ is the size of the largest set in the instance.)

Sheet 4: Exercises for Monday, February 12

  1. Let $G$ be a complete undirected graph with non-negative edge weights.

    a) Let $W$ denote the maximum weight of any edge in $G$.
    For each edge $e$, add $W$ to the weight of $e$.
    Let $G’$ denote the resulting weighted graph.

    Prove that the weights of $G’$ are metric, i.e., prove that they satisfy the triangle inequality.

    b) Argue that a TSP tour in $G$ is optimal, if and only if the corresponding tour in $G’$ is optimal.

    c) Why doesn’t this contradict Theorem 2.9?

  2. Describe an algorithm for finding an Euler tour in a graph where all vertices have even degree.

Sheet 5: Exercises for Friday, February 16

Read the Python tutorial [No]. You find some starting code from that page here.

Following the procedure for Benchmarking described there implement and compare as many TSP heuristics as you can. You find a list below, in bold the heuristics implemented in [No]. For a description of these heuristics see [Be].

Sheet 6: Exercises for Tuesday, February 20.

  1. In a 3-opt local search algorithm for the TSP how many possible ways are there to add three new edges once three edges have been removed in order to re-obtain an Hamiltonian tour? Justify your answer.

  2. Consider the traveling salesmane define on an incomplete graph. How could we encode the problem such that we can approach it with the construction heuristics and local search algorithms implemented for the complete version of the problem?

  3. Consider the asymmetric TSP. How can we encode this problem into a symmetric TSP, such that we can approach it with the construction heuristics and local search algorithms implemented for the symmetric version of the problem?

Sheet 7: Exercises for Friday, February 23.

Design a 3 exchange iterative improvement procedure for the TSP. The procedure must return a local optimum in the 3 exchange neighborhood. Implement the procedure in the framework made available in git.

A template to be completed is available in the file three_opt.py. You must only edit this file, you are not allowed to change the other files. When executed, your program will read the instance USA, construct a canonical tour and call your iterative improvement procedure. The benchmarking called from the main file will take care of assessing the quality of your solution.

Describe your algorithm in pseudocode in a one-page document edited with Latex. Use the Latex package algorithm2e.

Submit only the file three_opt.py and the PDF result of your Latex pseudocode at this portal. Keep your files anonymous! (The portal is likely to become available only during the night before Friday. Hence, you might have to submit during the class of Friday.)

You are encouraged to work in pairs at this assignment, in which case it is enough that only one submits.

Remember: start out with simple and even inefficient code without optimizing for efficiency. Only later, when your initial implementation is working and doing what you expect, start looking at efficiency improvements of your code (and consider the quality of the solutions as well).

Sheet 8: Exercises for Friday, March 9.

  1. Algorithm 3.1 is similar to the dynamic programming algorithm described in class, but may be more time and space efficient.
    Explain Algorithm 3.1.

  2. Solve Exercise 3.1.
    Hint: For proving the appoximation ratio it may be helpful to first consider the algorithm that chooses between the sets {$1,2,\ldots,k$} and {$k+1$}.

  3. Solve Exercise 3.6

Sheet 9: Exercises for Tuesday, April 10.

Encode the $k$-coloring problem as a SAT problem.

Sheet 10: Exercises for Monday, April 23.

  1. Solve Exercise 2.2

  2. In the lecture on Thursday, April 19, we proved that the approximation ratio of the local search algorithm and the List Scheduling algorithm is at most $2-\frac{1}{m}$. Prove that this bound is tight, i.e., prove that the ratio is at least $2-\frac{1}{m}$.

Sheet 11: Exercises for Monday, April 30.

Classfy the following scheduling applications:

  1. Gate Assignment at an Airport

    • Airline terminal at a airport with dozes of gates and hundreds of arrivals each day.

    • Gates and Airplanes have different characteristics

    • Airplanes follow a certain schedule

    • During the time the plane occupies a gate, it must go through a series of operations

    • There is a scheduled departure time (due date)

    • Performance measured in terms of on time departures.

  2. Scheduling Tasks in a Central Processing Unit (CPU)

    • Multitasking operating system

    • Schedule time that the CPU devotes to the different programs

    • Exact processing time unknown but an expected value might be known

    • Each program has a certain priority level

    • Tasks are often sliced into little pieces. They are then rotated such that low priority tasks of short duration do not stay for ever in the system.

    • Minimize expected time %, ie, sum of the weighted completion times for all tasks

  3. Paper bag factory

    • Basic raw material for such an operation are rolls of paper.

    • Production process consists of three stages: printing of the logo, gluing of the side of the bag, sewing of one end or both ends.

    • Each stage consists of a number of machines which are not necessarily identical.

    • Each production order indicates a given quantity of a specific bag that has to be produced and shipped by a committed shipping date or due date.

    • Processing times for the different operations are proportional to the number of bags ordered.

    • There are setup times when switching over different types of bags (colors, sizes) that depend on the similarities between the two consecutive orders

    • A late delivery implies a penalty that depends on the importance of the order or the client and the tardiness of the delivery.

Sheet 12: Exercises for Friday, May 18.

  1. Explain the derandomized version of the algorithm in Section 5.3.

  2. Do Exercise 5.7

Sheet 13: Exercises for Tuesday, May 22.

  1. Do Exercise 5.7
    Hint: Using $\lambda=n \cdot \ln n \cdot Z^*_{\text{LP}}$ may result in a $3 \ln n$-approximation algorithm.