On (1+ε) -approximate data reduction for the rural postman problem

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

1 Citation (Scopus)


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 b of vertices incident to an odd number of edges of R and the number b 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 (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.

Original languageEnglish
Title of host publicationMathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Proceedings
EditorsMichael Khachay, Panos Pardalos, Yury Kochetov
PublisherSpringer-Verlag GmbH and Co. KG
Number of pages16
ISBN (Print)9783030226282
Publication statusPublished - 1 Jan 2019
Event18th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2019 - Ekaterinburg, Russian Federation
Duration: 8 Jul 201912 Jul 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11548 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference18th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2019
CountryRussian Federation


  • Eulerian extension
  • Lossy kernelization
  • Parameterized complexity


Dive into the research topics of 'On (1+ε) -approximate data reduction for the rural postman problem'. Together they form a unique fingerprint.

Cite this