Zobrazeno 1 - 10
of 449
pro vyhledávání: '"Christofides algorithm"'
Autor:
Alok Chauhan
Publikováno v:
IEEE Access, Vol 12, Pp 144509-144518 (2024)
Travelling Salesman Problem (TSP) is NP-hard and therefore lacks efficient algorithm that provides optimal solution. So far, a benchmark in this area is Christofides’ Algorithm, which provides an upper bound of 3/2 for metric TSP. In this paper, it
Externí odkaz:
https://doaj.org/article/752d008f42c34e4589c94d0bcb5b95ea
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
Publikováno v:
IEEE Access, Vol 8, Pp 9782-9795 (2020)
Owing to the flexibility and low cost, cooperative Unmanned Aerial Vehicles(UAVs) have been attractive in multi-target positioning recently. Although it is popular and easy to accomplish, positioning based on trilateration method still faces challeng
Externí odkaz:
https://doaj.org/article/109239f86d024443ae4532883f8f9f24
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
Publikováno v:
Program Systems: Theory and Applications. 11:3-16
В работе описывается точный параллельный алгоритм для задачи коммивояжера, основанный на упрощенном алгоритме Балаша/Кристофидеса, ег
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::34e96ecd66bfc744166479577e80db2c
https://doi.org/10.25209/2079-3316-2020-11-4-3-16
https://doi.org/10.25209/2079-3316-2020-11-4-3-16
Autor:
Jens Vygen, Vera Traub
Publikováno v:
Operations Research Letters. 47:225-228
We give an improved analysis of the best-of-many Christofides algorithm with lonely edge deletion, which was proposed by Sebő and van Zuylen (2016). This implies an improved upper bound on the integrality ratio of the standard LP relaxation for the
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::bcfbeaebda0fe6684488ac7a4301bc7c
https://doi.org/10.1016/j.orl.2019.02.005
https://doi.org/10.1016/j.orl.2019.02.005
Autor:
Yu-Hsin Liu
Publikováno v:
Traveling Salesman Problem
The probabilistic travelling salesman problem (PTSP) is an extension of the well-known travelling salesman problem (TSP), which has been extensively studied in the field of combinatorial optimization. The goal of the TSP is to find the minimum length
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::93ad25609788841215611cab8664ad0d
http://www.intechopen.com/articles/show/title/solving_the_probabilistic_travelling_salesman_problem_based_on_genetic_algorithm_with_queen_selectio
http://www.intechopen.com/articles/show/title/solving_the_probabilistic_travelling_salesman_problem_based_on_genetic_algorithm_with_queen_selectio
Autor:
Alexander Löser, Lukas Behrendt, J. A. Gregor Lagodzinski, Marcus Wilhelm, Katrin Casel, Tobias Friedrich
Publikováno v:
Fundamentals of Computation Theory ISBN: 9783030865924
FCT
FCT
We generalize the tree doubling and Christofides algorithm to parameterized approximations for ATSP. The parameters we consider for the respective generalizations are upper bounded by the number of asymmetric distances, which yields algorithms to eff
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::41af164de8983cf8ae6bb5ce780813c0
https://doi.org/10.1007/978-3-030-86593-1_4
https://doi.org/10.1007/978-3-030-86593-1_4
Autor:
René van Bevern, Viktoriia A. Slugina
One of the most fundamental results in combinatorial optimization is the polynomial-time 3/2-approximation algorithm for the metric traveling salesman problem. It was presented by Christofides in 1976 and is well known as "the Christofides algorithm"
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::851495345dd93f2016b5a3b5f06f0ff7
http://arxiv.org/abs/2004.02437
http://arxiv.org/abs/2004.02437