### 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 |