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

René Van Bevern; Christian Komusiewicz; Manuel Sorge

doi:10.4230/OASIcs.ATMOS.2015.130

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	https://doi.org/10.4230/OASIcs.ATMOS.2015.130
Состояние	Опубликовано - 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 МАТЕМАТИКА

Доступ к документу

10.4230/OASIcs.ATMOS.2015.130

Link to publication in Scopus

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

Награды

Премния за лучшую статью на 15-ой конференции об алгоритмических подходах к моделям, оптимизации, и системам транспорта (17.09.2015, г. Парты, Греция)

ван Беверн, Рене Андреасович (Получатель), 17 сен 2015

Награда

Цитировать

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

Van Bevern, René ; Komusiewicz, Christian ; Sorge, Manuel. / Approximation algorithms for mixed, windy, and capacitated arc routing problems. 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, 2015. стр. 130-143 (OpenAccess Series in Informatics).

@inproceedings{a0a1c542ad59447f80b7200bebd463c8,

title = "Approximation algorithms for mixed, windy, and capacitated arc routing problems",

abstract = "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.",

keywords = "Chinese Postman, Combinatorial optimization, NPhard problem, Parameterized algorithm, Rural Postman, Transportation, Vehicle routing",

author = "{Van Bevern}, Ren{\'e} and Christian Komusiewicz and Manuel Sorge",

year = "2015",

month = sep,

day = "1",

doi = "10.4230/OASIcs.ATMOS.2015.130",

language = "English",

series = "OpenAccess Series in Informatics",

publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

pages = "130--143",

editor = "Marie Schmidt and Italiano, {Giuseppe F.}",

booktitle = "15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, ATMOS 2015",

address = "Germany",

note = "15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, ATMOS 2015 ; Conference date: 17-09-2015",

}

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

Approximation algorithms for mixed, windy, and capacitated arc routing problems. / Van Bevern, René; Komusiewicz, Christian; Sorge, Manuel.

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, 2015. стр. 130-143 (OpenAccess Series in Informatics; Том 48).

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

TY - GEN

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

AU - Van Bevern, René

AU - Komusiewicz, Christian

AU - Sorge, Manuel

PY - 2015/9/1

Y1 - 2015/9/1

N2 - 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.

AB - 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.

KW - Chinese Postman

KW - Combinatorial optimization

KW - NPhard problem

KW - Parameterized algorithm

KW - Rural Postman

KW - Transportation

KW - Vehicle routing

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

U2 - 10.4230/OASIcs.ATMOS.2015.130

DO - 10.4230/OASIcs.ATMOS.2015.130

M3 - Conference contribution

AN - SCOPUS:84946089718

T3 - OpenAccess Series in Informatics

SP - 130

EP - 143

BT - 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, ATMOS 2015

A2 - Schmidt, Marie

A2 - Italiano, Giuseppe F.

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, ATMOS 2015

Y2 - 17 September 2015

ER -

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