TU Berlin

Research Group Algorithmics and Computational ComplexityTalk 29.10.2015

isti-logo

Page Content

to Navigation

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.

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe