Аннотация
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 → … |
Предметные области OECD FOS+WOS
- 1.01 МАТЕМАТИКА
- 5.07 СОЦИАЛЬНАЯ И ЭКОНОМИЧЕСКАЯ ГЕОГРАФИЯ
ГРНТИ
- 27 МАТЕМАТИКА
Fingerprint
Подробные сведения о темах исследования «Approximation algorithms for mixed, windy, and capacitated arc routing problems». Вместе они формируют уникальный семантический отпечаток (fingerprint).Награды
-
Премния за лучшую статью на 15-ой конференции об алгоритмических подходах к моделям, оптимизации, и системам транспорта (17.09.2015, г. Парты, Греция)
ван Беверн, Р. А. (Получатель), 17 сен 2015
Награда