On approximate data reduction for the Rural Postman Problem: Theory and experiments. van Bevern, R., Fluschnik, T., & Tsidulko, O. Networks, 76(4):485-508, 2020. ![On approximate data reduction for the Rural Postman Problem: Theory and experiments [link]](https://bibbase.org/img/filetypes/link.svg "link")
Preprint Poster Slides Code doi abstract bibtex Given a graph G=(V,E) with edge weights ω:E→N∪0 and a subset R⊆E of required edges, the Rural Postman Problem (RPP) is to find a closed walk W* of minimum weight ω(W*) containing all edges of R. We prove that RPP is WK[1]-complete parameterized by the number and cost d=ω(W^*)-ω(R)+|W*|-|R| of edges traversed additionally to the required ones, that is, presumably cannot be polynomial-time reduced to solving instances of size polynomial in d. In contrast, denoting by b≤2d the number of vertices incident to an odd number of edges of R and by c≤d the number of connected components formed by the edges in R, we show how to reduce any RPP instance I to an RPP instance I' with 2b+O(c/ε) vertices in O(n³) 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). We make first steps towards a PSAKS for the parameter c.
@article{BFT20b,
author = {Ren{\'{e}} van Bevern and Till Fluschnik and Oxana
Tsidulko},
title = {On approximate data reduction for the {Rural Postman
Problem}: Theory and experiments},
year = {2020},
date = {2020-11-02},
journal = {Networks},
url_Preprint = {https://arxiv.org/abs/1812.10131},
url_Poster =
{https://figshare.com/articles/poster/On_approximate_data_reduction_for_the_Rural_Postman_Problem/13058969},
url_Slides =
{https://www.researchgate.net/publication/348297308_On_approximate_approximate_data_reduction_for_the_Rural_Postman_Problem_Theory_and_Experiments},
doi = {10.1002/net.21985},
volume = 76,
number = 4,
pages = {485-508},
url_Code = {https://gitlab.com/rvb/rpp-psaks},
abstract = {Given a graph G=(V,E) with edge weights ω:E→N∪{0}
and a subset R⊆E of required edges, the Rural
Postman Problem (RPP) is to find a closed walk W* of
minimum weight ω(W*) containing all edges of R. We
prove that RPP is WK[1]-complete parameterized by
the number and cost d=ω(W^*)-ω(R)+|W*|-|R| of edges
traversed additionally to the required ones, that
is, presumably cannot be polynomial-time reduced to
solving instances of size polynomial in d. In
contrast, denoting by b≤2d the number of vertices
incident to an odd number of edges of R and by c≤d
the number of connected components formed by the
edges in R, we show how to reduce any RPP instance I
to an RPP instance I' with 2b+O(c/ε) vertices in
O(n³) 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). We make
first steps towards a PSAKS for the parameter c.}
}
Downloads: 0
{"_id":"zBrQeo5gegNzyQJCL","bibbaseid":"vanbevern-fluschnik-tsidulko-onapproximatedatareductionfortheruralpostmanproblemtheoryandexperiments-2020","authorIDs":["2fwXJtKDCNhaSNr5s"],"author_short":["van Bevern, R.","Fluschnik, T.","Tsidulko, O."],"bibdata":{"bibtype":"article","type":"article","author":[{"firstnames":["René"],"propositions":["van"],"lastnames":["Bevern"],"suffixes":[]},{"firstnames":["Till"],"propositions":[],"lastnames":["Fluschnik"],"suffixes":[]},{"firstnames":["Oxana"],"propositions":[],"lastnames":["Tsidulko"],"suffixes":[]}],"title":"On approximate data reduction for the Rural Postman Problem: Theory and experiments","year":"2020","date":"2020-11-02","journal":"Networks","url_preprint":"https://arxiv.org/abs/1812.10131","url_poster":"https://figshare.com/articles/poster/On_approximate_data_reduction_for_the_Rural_Postman_Problem/13058969","url_slides":"https://www.researchgate.net/publication/348297308_On_approximate_approximate_data_reduction_for_the_Rural_Postman_Problem_Theory_and_Experiments","doi":"10.1002/net.21985","volume":"76","number":"4","pages":"485-508","url_code":"https://gitlab.com/rvb/rpp-psaks","abstract":"Given a graph G=(V,E) with edge weights ω:E→N∪0 and a subset R⊆E of required edges, the Rural Postman Problem (RPP) is to find a closed walk W* of minimum weight ω(W*) containing all edges of R. We prove that RPP is WK[1]-complete parameterized by the number and cost d=ω(W^*)-ω(R)+|W*|-|R| of edges traversed additionally to the required ones, that is, presumably cannot be polynomial-time reduced to solving instances of size polynomial in d. In contrast, denoting by b≤2d the number of vertices incident to an odd number of edges of R and by c≤d the number of connected components formed by the edges in R, we show how to reduce any RPP instance I to an RPP instance I' with 2b+O(c/ε) vertices in O(n³) 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). We make first steps towards a PSAKS for the parameter c.","bibtex":"@article{BFT20b,\n author =\t {Ren{\\'{e}} van Bevern and Till Fluschnik and Oxana\n Tsidulko},\n title =\t {On approximate data reduction for the {Rural Postman\n Problem}: Theory and experiments},\n year =\t {2020},\n date =\t {2020-11-02},\n journal =\t {Networks},\n url_Preprint = {https://arxiv.org/abs/1812.10131},\n url_Poster =\n {https://figshare.com/articles/poster/On_approximate_data_reduction_for_the_Rural_Postman_Problem/13058969},\n url_Slides =\n {https://www.researchgate.net/publication/348297308_On_approximate_approximate_data_reduction_for_the_Rural_Postman_Problem_Theory_and_Experiments},\n doi =\t\t {10.1002/net.21985},\n volume =\t 76,\n number =\t 4,\n pages =\t {485-508},\n url_Code =\t {https://gitlab.com/rvb/rpp-psaks},\n abstract =\t {Given a graph G=(V,E) with edge weights ω:E→N∪{0}\n and a subset R⊆E of required edges, the Rural\n Postman Problem (RPP) is to find a closed walk W* of\n minimum weight ω(W*) containing all edges of R. We\n prove that RPP is WK[1]-complete parameterized by\n the number and cost d=ω(W^*)-ω(R)+|W*|-|R| of edges\n traversed additionally to the required ones, that\n is, presumably cannot be polynomial-time reduced to\n solving instances of size polynomial in d. In\n contrast, denoting by b≤2d the number of vertices\n incident to an odd number of edges of R and by c≤d\n the number of connected components formed by the\n edges in R, we show how to reduce any RPP instance I\n to an RPP instance I' with 2b+O(c/ε) vertices in\n O(n³) time so that any α-approximate solution for I'\n gives an α(1+ε)-approximate solution for I, for any\n α≥1 and ε>0. That is, we provide a polynomial-size\n approximate kernelization scheme (PSAKS). We make\n first steps towards a PSAKS for the parameter c.}\n}\n\n","author_short":["van Bevern, R.","Fluschnik, T.","Tsidulko, O."],"key":"BFT20b","id":"BFT20b","bibbaseid":"vanbevern-fluschnik-tsidulko-onapproximatedatareductionfortheruralpostmanproblemtheoryandexperiments-2020","role":"author","urls":{" preprint":"https://arxiv.org/abs/1812.10131"," poster":"https://figshare.com/articles/poster/On_approximate_data_reduction_for_the_Rural_Postman_Problem/13058969"," slides":"https://www.researchgate.net/publication/348297308_On_approximate_approximate_data_reduction_for_the_Rural_Postman_Problem_Theory_and_Experiments"," code":"https://gitlab.com/rvb/rpp-psaks"},"metadata":{"authorlinks":{"van bevern, r":"https://rvb.su/"}}},"bibtype":"article","biburl":"http://rvb.su/rvb.bib","creationDate":"2021-01-06T14:24:56.569Z","downloads":6,"keywords":[],"search_terms":["approximate","data","reduction","rural","postman","problem","theory","experiments","van bevern","fluschnik","tsidulko"],"title":"On approximate data reduction for the Rural Postman Problem: Theory and experiments","year":2020,"dataSources":["SMwzc9Bzq5Np5ikev","G5GefJqqu2DtnCZXz"]}