Seminar za računarstvo i primenjenu matematiku, 1. decembar 2020.

• 30. Novembar,  2020
• Komentari (0)

Naredni sastanak Seminara biće održan u utorak, 1. decembra 2020, u sali 301f Matematičkog instituta SANU sa početkom u 14:15.

Predavač: Vera Kovačević-Vujčić, Fakultet organizacionih nauka

Naslov predavanja: COMPLEXITY INDICES FOR THE TRAVELING SALESMAN PROBLEM

Apstrakt:
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.

Napomena:
Zbog trenutne epidemiološke situacije, maksimalnan broj slušalaca u sali je pet (uključujući predavača i organizatore seminara). Predavanja se mogu pratiti na daljinu preko linka https://miteam.mi.sanu.ac.rs/asset/AR4aSMvvmadtRSKPF ukoliko predavač da svoju saglasnost.

---