Author Archives: ingeli

Mandatory exercise

I’ve got some questions about the mandatory exercise from some of you, so here are some clarifications.

As we talked about at the end of the exercise class, the problem is different from metric TSP in several ways.

  • It is not a metric. There is no triangle inequality and there is not necessarily direct hiking paths between all pairs of villages.
  • You are allowed to visit each village as many times as you want, as long as you visit each of them at least once.
  • The solution (OPT) is a path, not a cycle, so the way we proved that M is at most 1/2 OPT no longer holds. You have to modify this proof if you want to use a matching. 

Just removing the last edge in a TSP tour found with Christofides’ algorithm is not going to work (you should try to convince yourself about this).

 

-Inge

Office hours and approximation algorithms

I have office hours Fridays at 12.15-13.00.

We started on approximation algorithms today. It is a new topic and it requires another way of thinking that is hard in the beginning. But keep up the good spirit and hard work 🙂

One of the links in the literature list did not work anymore – that is fixed now.

Next time we will talk about and stable matchings and Christofides’ algorithm for TSP.

When you prove that your algorithm in the mandatory assignment is a 2-approximation algorithm remember to prove that it is a polynomial time algorithm, that the solution is valid and that the approximation factor is 2.

-Inge

Exam dates

The exam is on May 23 and 24.

If you have other exams on one of the days and therefore are not able to participate that day, then send me an email before May 15.

We will send the list out shortly after that, so you know which day you are on.

-Inge

Mandatory Exercise: Exercise update

In the mandatory exercises it says “Analyze the running time of a sequence of n Create-Tree and m Return-Depth and Merge-Tree operations in your data structure”.

That should be understood as ANY mixed sequence of n Create-Tree, m Return-Depth, and m Merge-Tree operations,  i.e. the operations can be interleaved.

-Inge