TU Berlin

Algorithmics and Computational Complexity Research GroupTalk 18.04.2019

isti-logo

Page Content

to Navigation

On (1 + ε)-approximate data reduction for the Rural Postman Problem

Till Fluschnik (TU Berlin)

 

Given a graph G = (V, E) with edge weights and a subset R ⊆ E of required edges, the NP-hard Rural Postman Problem (RPP) is to find a closed walk of minimum total weight containing all edges of R. The number b of vertices incident to an odd number of edges of R and the number c of connected components formed by the edges in R are both bounded from above by the  number of edges that has to be traversed additionally to the required ones. We show how to reduce any RPP instance I to an RPP instance I' with 2b + O(c/ε) vertices in O(n^3) time so that any α-approximate solution for I' gives an α(1 + ε)-approximate solution for I, for any α ≥ 1 and ε > 0. That is, we provide a polynomial-size approximate kernelization scheme (PSAKS).

 

Date
Speaker
Location
Language
18.04.2019
16:15
Till Fluschnik
TEL 512
English

Back to the research colloquium site.

To top

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe