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

René Van Bevern, Christian Komusiewicz, Manuel Sorge

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

2 Citations (Scopus)

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.

Original languageEnglish
Title of host publication15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, ATMOS 2015
EditorsMarie Schmidt, Giuseppe F. Italiano
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages130-143
Number of pages14
ISBN (Electronic)9783939897996
DOIs
Publication statusPublished - 1 Sep 2015
Event15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, ATMOS 2015 - Patras, Greece
Duration: 17 Sep 2015 → …

Publication series

NameOpenAccess Series in Informatics
Volume48
ISSN (Print)2190-6807

Conference

Conference15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, ATMOS 2015
CountryGreece
CityPatras
Period17.09.2015 → …

Keywords

  • Chinese Postman
  • Combinatorial optimization
  • NPhard problem
  • Parameterized algorithm
  • Rural Postman
  • Transportation
  • Vehicle routing

OECD FOS+WOS

  • 1.01 MATHEMATICS
  • 5.07 SOCIAL AND ECONOMIC GEOGRAPHY

State classification of scientific and technological information

  • 27 MATHEMATICS

Fingerprint

Dive into the research topics of 'Approximation algorithms for mixed, windy, and capacitated arc routing problems'. Together they form a unique fingerprint.

Cite this