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. ed. / Marie Schmidt; Giuseppe F. Italiano. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2015. p. 130-143 (OpenAccess Series in Informatics; Vol. 48).
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
Harvard
Van Bevern, R, Komusiewicz, C & Sorge, M 2015,
Approximation algorithms for mixed, windy, and capacitated arc routing problems. in M Schmidt & GF Italiano (eds),
15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, ATMOS 2015. OpenAccess Series in Informatics, vol. 48, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, pp. 130-143, 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, ATMOS 2015, Patras, Greece,
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. In M. Schmidt, & G. F. Italiano (Eds.),
15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, ATMOS 2015 (pp. 130-143). (OpenAccess Series in Informatics; Vol. 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. In Schmidt M, Italiano GF, editors, 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, ATMOS 2015. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2015. p. 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. editor / Marie Schmidt ; Giuseppe F. Italiano. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2015. pp. 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 -
