@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",

}