Colloquium of Research Area KL
Colloquium of Research Area KL

Colloquium of Research Area KL

Date: January 25, 2013
Venue:  Seminar room 1st floor, Arithmeum, Lennéstr. 2, Bonn

Programm:

15:45 Coffee and Tee (Lounge 2nd floor, Arithmeum, Lennéstr. 2)
16:15 Jens Vygen: Short presentation of the research area
16:20 Jens Vygen: New approximation algorithms for the traveling salesman problem
17:05 Coffee break
17:30 Jens Franke: A tale of two primality tests

Abstracts:

Jens Vygen: New approximation algorithms for the TSP

Christofides' approximation guarantee of 3/2 for the metric TSP remains the best known since 1976. Recently, there have been advances for an interesting special case: the graphic TSP. We introduce several new techniques and use them to improve the approximation guarantee to 7/5. This is joint work with András Sebő.

Jens Franke: A tale of two primality tests

We describe Mihailescu's proposal to merge the classical Jacobi sum and elliptic curve primality tests, and our completion and implementation of that proposal.