Семинар за рачунарство и примењену математику, 1. децембар 2020.

• 30. Новембар, 2020
• Коментари (0)

Наредни састанак Семинара биће одржан у уторак, 1. децембра 2020, у сали 301ф Математичког института САНУ са почетком у 14:15.

Предавач: Вера Ковачевић-Вујчић, Факултет организационих наука

Наслов предавања: COMPLEXITY INDICES FOR THE TRAVELING SALESMAN PROBLEM

Апстракт:
We consider the symmetric traveling salesman problem (TSP) with instances represented by complete graphs G with distances between cities as edge weights. A complexity index is an invariant of an instance I by which we predict, in a statistical sense, the execution time of an exact TSP algorithm for I.

In the paper: Cvetković D., Čangalović M., Dražić Z., Kovačević-Vujčić V., "Complexity indices for the traveling salesman problem based on short edge subgraphs", Central European Journal of Operations Research, 26(2018), No. 3, 759-769, we have considered some short edge subgraphs of G and defined several new invariants related to their connected components. Extensive computational experiments with instances on 50 vertices with the uniform distribution of integer edge weights in the interval [1,100] show that there exists correlation between the sequences of selected invariants and the sequence of execution times of the well-known TSP Solver Concorde. In this talk we report the extension of the above considerations for instances up to 100 vertices.

This is joint work with Dragoš Cvetković, Faculty of Electrical Engineering, University of Belgrade and Mathematical Institute SANU and Zorica Dražić, Faculty of Mathematics, University of Belgrade.

Напомена:
Због тренутне епидемиолошке ситуације, максималнан број слушалаца у сали је пет (укључујући предавача и организаторе семинара). Предавања се могу пратити на даљину преко линка https://miteam.mi.sanu.ac.rs/asset/AR4aSMvvmadtRSKPF уколико предавач да своју сагласност.