Today started the 2 month Summer Program on Cryptography at the Simons Institute in Berkeley. The Simons Institute for the Theory of Computing is an exciting new venue for collaborative research in theoretical computer science. The Institute typically hosts two concurrent programs per semester, where each is led by a small group of organizers who are recognized experts in their fields, and involves about 40-50 invited long-term participants (a mix of senior and junior researchers) who spend at least one month (usually longer) at the Institute.
The Cryptography program started today with an one week bootcamp that is intended to bring every participant on the same page regarding the recent developments in crypto. This day was extremely instructive because the lectures were not only very up to date but also very well taught, as opposed to the standard conference talk.
And what is really amazing is that the lectures were recorded and are now available online! So have a look at them!
Two days ago I published my blog entry My Solution to a Question from Jack Edmonds: Reduction of the Shortest Path Problem to the Assignment Problem. Here I will give an example to illustrate how the reduction works.
So let's start with the graph shown in figure 1.
We will construct the bipartite graph shown in figure 2. On the left is the set X, containing copies of all inner nodes and the node t. On the right is the set Y, containing a second copy of all inner nodes and the node s. For each edge (a,b) in the initial graph we add an edge from the node that corresponds to a on the right side to the node that corresponds to b on the left side. In addition to that, we link all pairs, which are the blue horizontal lines. Continue reading
I am very happy that I had the chance today to attend a lecture held by Jack Edmonds, who is regarded as one of the most important contributors to the field of combinatorial optimization.
During his talk, Jack asked us to think about how to reduce the shortest path problem on directed graphs with rational costs on the edges to the assignment problem. I thought a bit about it and want to present my solution here.
First of all, let's recap what the shortest path problem and the assignment problem is. Continue reading
For the seminar "Selected Fields in Computer Science" offered by Prof. Dr. R. Schrader in summer 2013 at the University of Cologne I dealt with the concept of local search and presented the resulting K-Opt Algorithm for the NP-complete Travelling salesman problem that gives results with a quality determined by the choice of k.
Furthermore my seminar paper covered the Lin-Kernighan-Heuristic which is an in the real world often used heuristic algorithm for getting approximate solutions for the TSP that are usually > 95% of the optimum for real world data.
The seminar paper is in German and can be downloaded here: K-Opt and the Lin-Kernighan-Heuristic for the Traveling Salesman Problem (German)