Standard

Constant-Factor Approximation Algorithms for a Series of Combinatorial Routing Problems Based on the Reduction to the Asymmetric Traveling Salesman Problem. / Khachay, M. Yu.; Neznakhina, E. D.; Ryzhenko, K. V.
в: Proceedings of the Steklov Institute of Mathematics, Том 319, № S1, 01.12.2022, стр. S140-S155.

Результаты исследований: Вклад в журнал › Статья › Рецензирование

Harvard

Khachay, MY, Neznakhina, ED & Ryzhenko, KV 2022, 'Constant-Factor Approximation Algorithms for a Series of Combinatorial Routing Problems Based on the Reduction to the Asymmetric Traveling Salesman Problem', Proceedings of the Steklov Institute of Mathematics, Том. 319, № S1, стр. S140-S155. https://doi.org/10.1134/S0081543822060128

APA

Khachay, M. Y., Neznakhina, E. D., & Ryzhenko, K. V. (2022). Constant-Factor Approximation Algorithms for a Series of Combinatorial Routing Problems Based on the Reduction to the Asymmetric Traveling Salesman Problem. Proceedings of the Steklov Institute of Mathematics, 319(S1), S140-S155. https://doi.org/10.1134/S0081543822060128

Vancouver

Khachay MY, Neznakhina ED, Ryzhenko KV. Constant-Factor Approximation Algorithms for a Series of Combinatorial Routing Problems Based on the Reduction to the Asymmetric Traveling Salesman Problem. Proceedings of the Steklov Institute of Mathematics. 2022 дек. 1;319(S1):S140-S155. doi: 10.1134/S0081543822060128

Author

Khachay, M. Yu. ; Neznakhina, E. D. ; Ryzhenko, K. V. / Constant-Factor Approximation Algorithms for a Series of Combinatorial Routing Problems Based on the Reduction to the Asymmetric Traveling Salesman Problem. в: Proceedings of the Steklov Institute of Mathematics. 2022 ; Том 319, № S1. стр. S140-S155.

BibTeX

@article{1d36264436644a6691e3dab2b74aabf5,
title = "Constant-Factor Approximation Algorithms for a Series of Combinatorial Routing Problems Based on the Reduction to the Asymmetric Traveling Salesman Problem",
abstract = "For the first time, algorithms with constant performance guarantees are substantiated for a series of asymmetric routing problems of combinatorial optimization: the Steiner cycle problem (SCP), the generalized traveling salesman problem (GTSP), the capacitated vehicle routing problem with unsplittable customer demands (CVRP-UCD), and the prize collecting traveling salesman problem (PCTSP). The presented results are united by the property that they all rely on polynomial cost-preserving reduction to appropriate instances of the asymmetric traveling salesman problem (ATSP) and on the (22 + epsilon)-approximation algorithm for this classical problem proposed by O. Svensson and V. Traub in 2019.",
author = "Khachay, {M. Yu.} and Neznakhina, {E. D.} and Ryzhenko, {K. V.}",
note = "This work was supported by the Russian Science Foundation (project no. 22-21-00672, https://rscf.ru/project/22-21-00672)",
year = "2022",
month = dec,
day = "1",
doi = "10.1134/S0081543822060128",
language = "English",
volume = "319",
pages = "S140--S155",
journal = "Proceedings of the Steklov Institute of Mathematics",
issn = "0081-5438",
publisher = "Pleiades Publishing",
number = "S1",

}

RIS

TY - JOUR

T1 - Constant-Factor Approximation Algorithms for a Series of Combinatorial Routing Problems Based on the Reduction to the Asymmetric Traveling Salesman Problem

AU - Khachay, M. Yu.

AU - Neznakhina, E. D.

AU - Ryzhenko, K. V.

N1 - This work was supported by the Russian Science Foundation (project no. 22-21-00672, https://rscf.ru/project/22-21-00672)

PY - 2022/12/1

Y1 - 2022/12/1

N2 - For the first time, algorithms with constant performance guarantees are substantiated for a series of asymmetric routing problems of combinatorial optimization: the Steiner cycle problem (SCP), the generalized traveling salesman problem (GTSP), the capacitated vehicle routing problem with unsplittable customer demands (CVRP-UCD), and the prize collecting traveling salesman problem (PCTSP). The presented results are united by the property that they all rely on polynomial cost-preserving reduction to appropriate instances of the asymmetric traveling salesman problem (ATSP) and on the (22 + epsilon)-approximation algorithm for this classical problem proposed by O. Svensson and V. Traub in 2019.

AB - For the first time, algorithms with constant performance guarantees are substantiated for a series of asymmetric routing problems of combinatorial optimization: the Steiner cycle problem (SCP), the generalized traveling salesman problem (GTSP), the capacitated vehicle routing problem with unsplittable customer demands (CVRP-UCD), and the prize collecting traveling salesman problem (PCTSP). The presented results are united by the property that they all rely on polynomial cost-preserving reduction to appropriate instances of the asymmetric traveling salesman problem (ATSP) and on the (22 + epsilon)-approximation algorithm for this classical problem proposed by O. Svensson and V. Traub in 2019.

UR - https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=tsmetrics&SrcApp=tsm_test&DestApp=WOS_CPL&DestLinkType=FullRecord&KeyUT=000944216100012

UR - http://www.scopus.com/inward/record.url?partnerID=8YFLogxK&scp=85163006876

U2 - 10.1134/S0081543822060128

DO - 10.1134/S0081543822060128

M3 - Article

VL - 319

SP - S140-S155

JO - Proceedings of the Steklov Institute of Mathematics

JF - Proceedings of the Steklov Institute of Mathematics

SN - 0081-5438

IS - S1

ER -

ID: 37085125