Approximation algorithms for mixed, windy, and capacitated arc routing problems

René Van Bevern, Christian Komusiewicz, Manuel Sorge

Результат исследования: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование

2 Цитирования (Scopus)

Аннотация

We show that any α(n)-approximation algorithm for the n-vertex metric asymmetric Traveling Salesperson problem yields O(α(C))-approximation algorithms for various mixed, windy, and capacitated arc routing problems. Herein, C is the number of weakly-connected components in the subgraph induced by the positive-demand arcs, a number that can be expected to be small in applications. In conjunction with known results, we derive constant-factor approximations if C ε O(log n) and O(log C/log log C) -approximations in general.

Язык оригиналаанглийский
Название основной публикации15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, ATMOS 2015
РедакторыMarie Schmidt, Giuseppe F. Italiano
ИздательSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Страницы130-143
Число страниц14
ISBN (электронное издание)9783939897996
DOI
СостояниеОпубликовано - 1 сен 2015
Событие15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, ATMOS 2015 - Patras, Греция
Продолжительность: 17 сен 2015 → …

Серия публикаций

НазваниеOpenAccess Series in Informatics
Том48
ISSN (печатное издание)2190-6807

Конференция

Конференция15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, ATMOS 2015
СтранаГреция
ГородPatras
Период17.09.2015 → …

ГРНТИ

  • 27 МАТЕМАТИКА

Fingerprint Подробные сведения о темах исследования «Approximation algorithms for mixed, windy, and capacitated arc routing problems». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать

    Van Bevern, R., Komusiewicz, C., & Sorge, M. (2015). Approximation algorithms for mixed, windy, and capacitated arc routing problems. В M. Schmidt, & G. F. Italiano (Ред.), 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, ATMOS 2015 (стр. 130-143). (OpenAccess Series in Informatics; Том 48). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/OASIcs.ATMOS.2015.130