Research Talk: Efficient Variants of the 2-Opt Heuristic for the TSPThe 2-opt heuristic is a simple and popular local search heuristic for the Traveling Salesperson Problem (TSP). Albeit its performance in practice, it has exponential worst-case running-time. We consider two restrictions of the 2-opt heuristic that run in polynomial time in the worst case and analyze their approximation performance.Read more- Graduate Seminar: Serge Johanns & Wick WijnholdSerge Johanns: Efficient Deductive Synthesis of Programs with Pointers
Wick Wijnhold: An efficient algorithm for certifying nongraphicness of matroidsRead more
