An O(log n/log log n)-Approximation Algorithm for the Asymmetric Traveling Salesman Problem
A Asadpour, MX Goemans, A Mądry… - Operations …, 2017 - pubsonline.informs.org
We present a randomized O (log n/log log n)-approximation algorithm for the asymmetric
traveling salesman problem (ATSP). This provides the first asymptotic improvement over the …
traveling salesman problem (ATSP). This provides the first asymptotic improvement over the …
A constant-factor approximation algorithm for the asymmetric traveling salesman problem
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 …
problem (ATSP). Our approximation guarantee is analyzed with respect to the standard LP …
Relationship between examination questions and bloom's taxonomy
KO Jones, J Harland, JMV Reid… - 2009 39th IEEE frontiers …, 2009 - ieeexplore.ieee.org
Written examination is a conventional yet universal tool to evaluate the student's
performance in a subject area, where the required cognitive ability is defined through items …
performance in a subject area, where the required cognitive ability is defined through items …
Reducing path TSP to TSP
We present a black-box reduction from the path version of the Traveling Salesman Problem
(Path TSP) to the classical tour version (TSP). More precisely, we show that given an α …
(Path TSP) to the classical tour version (TSP). More precisely, we show that given an α …
SDN-based traffic aware placement of NFV middleboxes
Network function virtualization (NFV) enables flexible deployment of middleboxes as virtual
machines running on general hardware. Since different middleboxes may change the …
machines running on general hardware. Since different middleboxes may change the …
Effective-resistance-reducing flows, spectrally thin trees, and asymmetric TSP
We show that the integrality gap of the natural LP relaxation of the Asymmetric Traveling
Salesman Problem is polyloglog (n). In other words, there is a polynomial time algorithm that …
Salesman Problem is polyloglog (n). In other words, there is a polynomial time algorithm that …
An improved approximation algorithm for ATSP
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 …
problem by Svensson, Tarnawski, and Végh [STOC 2018]. We improve on each part of this …
Complexity and approximation in reoptimization
G Ausiello, V Bonifaci, B Escoffier - … and Logic in the Real World, 2011 - World Scientific
In this chapter the following model is considered: We assume that an instance I of a
computationally hard optimization problem has been solved and that we know the optimum …
computationally hard optimization problem has been solved and that we know the optimum …
An improved approximation algorithm for the asymmetric traveling salesman problem
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 …
problem by Svensson, Tarnawski, and Végh J. ACM, 67 (2020), 37. We improve on each …
The asymmetric traveling salesman problem on graphs with bounded genus
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms : The
Asymmetric Traveling Salesman Problem on Page 1 The Asymmetric Traveling Salesman …
Asymmetric Traveling Salesman Problem on Page 1 The Asymmetric Traveling Salesman …