[Dottorcomp] Seminar May 26th

[Ambrogio Maria Bernardelli]

 Ciao everyone :)

Just a quick note to let you know that tomorrow Eleonora Vercesi will be
giving a seminar. Here are the details:

*Seminar title:* Easy to see, hard to prove
*Date:* May 26th, 2025 -14:00, Aula E9
*Abstract:* In this talk, we will discuss some recent results we have
obtained on hard instances of the Travelling Salesperson Problem (TSP),
 from different perspectives. A common theme through the talk is that,
while the problems may initially appear simple or intuitive, their
technical details often turn out to be very intricate. We will also present
several open questions, some of which may be suitable as Master's thesis
topics. We begin by introducing the classic Dantzig–Fulkerson–Johnson (DFJ)
formulation of the TSP, which is conjectured to have an integrality gap of
4/3. Since its introduction in 1954, however, this conjecture has remained
unproven. We will explain how we have (partially) proved the bound, without
relying on a lemma that, although it seems obvious, proved too difficult
for us to establish. This naturally leads to several compelling open
problems. Next, we focus on subtour elimination constraints (SECs), the
novel and central feature of the DFJ formulation. We present an algorithm
that computes the minimum number of SECs required to solve a given
instance, and then explore worst-case scenarios. Are there instances that
require 2ⁿ SECs? This question turns out to be far more complex than one
might expect. We show examples of instances that can be solved with only
O(n) SECs, and others that appear to require O(n²), though no formal proof
currently exists. We then broaden our view and ask a more general question:
given a heuristic for the TSP, is it possible to automatically construct a
counterexample where the heuristic fails—or at least to prove that one must
exist for a given input size? While some specific cases are easy to settle,
generalizing these results remains a difficult and open problem. The
lecture will be as interactive as possible, encouraging questions and
discussion throughout. Given time constraints, students will be invited to
choose the order of the topics at the beginning of the session.

A presto,
Ambrogio