@inproceedings{a02f553138b84869a6080a98380da32a,
title = "On (1+ε) -approximate data reduction for the rural postman problem",
abstract = "Given a graph G=(V,E) with edge weights and a subset (formula presented) 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{\^A} b of vertices incident to an odd number of edges of R and the number b of connected components formed by the edges in{\^A} 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{\^A} I to an RPP instance I' with (formula presented) vertices in O(n)3 time so that any α -approximate solution for I' gives an (formula presented). -approximate solution for I, for any (formula presented). That is, we provide a polynomial-size approximate kernelization scheme (PSAKS). We make first steps towards a PSAKS with respect to the parameter c.",
keywords = "Eulerian extension, Lossy kernelization, Parameterized complexity, EULERIAN EXTENSION, APPROXIMATION, BOUNDS",
author = "{van Bevern}, Ren{\'e} and Till Fluschnik and Tsidulko, {Oxana Yu}",
year = "2019",
month = jan,
day = "1",
doi = "10.1007/978-3-030-22629-9_20",
language = "English",
isbn = "9783030226282",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer-Verlag GmbH and Co. KG",
pages = "279--294",
editor = "Michael Khachay and Panos Pardalos and Yury Kochetov",
booktitle = "Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Proceedings",
address = "Germany",
note = "18th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2019 ; Conference date: 08-07-2019 Through 12-07-2019",
}