We give a constant-factor approximation algorithm for the asymmetric traveling salesman
problem (ATSP). Our approximation guarantee is analyzed with respect to the standard LP …

We revisit the constant-factor approximation algorithm for the asymmetric traveling salesman
problem by Svensson, Tarnawski, and Végh [STOC 2018]. We improve on each part of this …

We revisit the constant-factor approximation algorithm for the asymmetric traveling salesman
problem by Svensson, Tarnawski, and Végh J. ACM, 67 (2020), 37. We improve on each …

The traveling salesman problem is the probably most famous problem in combinatorial
optimization. Given a graph G and nonnegative edge costs, we want to find a closed walk in …

This article gives a short overview of my dissertation, where new algorithms are given for two
fundamental graph problems. We develop novel ways of using linear programming …

We study the edge-frequencies computed with frequency quadrilaterals for traveling
salesman problem. The edge-frequency of an edge in the optimal Hamiltonian cycle is …

Предметом исследования данной диссертационной работы является аппроксимация
метрических постановок задачи маршрутизации транспортных средств ограниченной …

In dieser Arbeit werden neue Algorithmen für zwei grundlegende Graphenprobleme
vorgestellt. Mit Hilfe von linearen Programmen–darunter auch Programme exponentieller …

The 13th International Computer Science Symposium in Russia (CSR 2018) was held
during June 6–10, 2018, in Moscow, Russia. The symposium was organized by the Higher …

Abstract The Traveling Salesman Problem is the task of finding a shortest cyclical tour which
visits all vertices of a weighted graph. We consider approximation algorithms for ATSP–the …