[Mittagsseminar TI] Fwd: Invitation to the Defense of my Bachelor's Thesis
Dear TIs,
this defense, possibly of interest, planned tomorrow in T9.
Best,
Laszlo
-------- Forwarded Message --------
Subject: Re: [i-prof] [i-studi] Invitation to the Defense of my
Bachelor's Thesis
From: Feliks Vdovichenko <feliv01@zedat.fu-berlin.de>
Dear all,
the room of the defense was changed to room 137 also known as the
conference room, upstairs at Takustraße 9. The time remains unchanged,
so Friday, 24.10.2025 at 12:00.
Sincerely,
Feliks Vdovichenko
Abstract:
The approximation of the Travelling Salesperson Problem is a widely
studied field where even simple approaches seem to promise good results.
In this thesis, we examine two different approaches to approximating the
Maximum TSP. The first, the Graph Patch Heuristic, attempts to find a
solution by patching a maximum-weight cycle cover into a singular cycle.
The second, called the Tunnelling Algorithm, builds on the idea of
approximating the Euclidean norm with a metric defined by a polytope.
Despite their drastically different methodologies, we find that both
approaches reduce to a similar sub-problem and yield similar approximation
ratios. While the Graph Patch Heuristic seems to outperform the Tunnelling
Algorithm with larger input sizes and dimensions, we find that the
Tunnelling Algorithm actually solves the Max TSP in polynomial time for
common norms such as $L_1$ and $L_\infty$. This thesis expands on some of
the nuances of both algorithms, presenting them in a self-contained
manner.
