direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

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

Zusatzinformationen / Extras