Monthly Archives: March 2014

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