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

Наредни састанак Семинара биће одржан у уторак, 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
уколико предавач да своју сагласност.