Standard
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).
Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
Harvard
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
APA
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
Vancouver
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). doi: 10.4230/OASIcs.ATMOS.2015.130
Author
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).
BibTeX
@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",
}
RIS
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
UR - https://elibrary.ru/item.asp?id=24968474
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 -
