direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

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

Manuel Sorge, TU Berlin

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 is in O(log n) and O(log(C)/log(log(C)))-approximations in general.

This is joint work with René van Bevern and Christian Komusiewicz.

Date
Speaker
Location
Language
29.10.2015
16:15
Manuel Sorge
TEL 512
English

Back to the research colloquium site.

Zusatzinformationen / Extras