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.