direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

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).


Till Fluschnik
TEL 512

Back to the research colloquium site. [1]

To top

------ Links: ------

Zusatzinformationen / Extras