Discrete Applied Math Seminar by Stjin Cambie:The Average Solution of a TSP Instance in a Graph

Speaker: Stjin Cambie, Katholieke Universiteit at Leuven, Belgium

Title: The Average Solution of a TSP Instance in a Graph

Abstract:

In many practical situations (mostly logistics- or routing-related), one wants to find the most efficient route visiting some places.
For example, in a warehouse, one may want to pick the items from different spots that are necessary for a delivery.
In this case, one needs to solve a so-called TSP (travelling salesman problem) instance.
This is a well-studied topic, where in the abstract form, one has a (possibly weighted) graph and one needs to find the shortest walk visiting a certain list of vertices.

When constructing  the network; city plan or some circuit design, one may aim that the logistics will be efficient in most of the cases.
That is, one may want to know the graphs for which the TSP instance will have a small cost.
As such, it is interesting to study the graphs that have extremal solutions for the average cost of the TSP instance.

In this talk, we give some definitions and ideas about the extremal graphs, and observe relations with other concepts.

 

Discrete Applied Math Seminar

Request Zoom Link