Standard

On (1+ε) -approximate data reduction for the rural postman problem. / van Bevern, René; Fluschnik, Till; Tsidulko, Oxana Yu.

Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Proceedings. ed. / Michael Khachay; Panos Pardalos; Yury Kochetov. Springer-Verlag GmbH and Co. KG, 2019. p. 279-294 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11548 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

Harvard

van Bevern, R, Fluschnik, T & Tsidulko, OY 2019, On (1+ε) -approximate data reduction for the rural postman problem. in M Khachay, P Pardalos & Y Kochetov (eds), Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11548 LNCS, Springer-Verlag GmbH and Co. KG, pp. 279-294, 18th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2019, Ekaterinburg, Russian Federation, 08.07.2019. https://doi.org/10.1007/978-3-030-22629-9_20

APA

van Bevern, R., Fluschnik, T., & Tsidulko, O. Y. (2019). On (1+ε) -approximate data reduction for the rural postman problem. In M. Khachay, P. Pardalos, & Y. Kochetov (Eds.), Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Proceedings (pp. 279-294). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11548 LNCS). Springer-Verlag GmbH and Co. KG. https://doi.org/10.1007/978-3-030-22629-9_20

Vancouver

van Bevern R, Fluschnik T, Tsidulko OY. On (1+ε) -approximate data reduction for the rural postman problem. In Khachay M, Pardalos P, Kochetov Y, editors, Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Proceedings. Springer-Verlag GmbH and Co. KG. 2019. p. 279-294. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-22629-9_20

Author

van Bevern, René ; Fluschnik, Till ; Tsidulko, Oxana Yu. / On (1+ε) -approximate data reduction for the rural postman problem. Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Proceedings. editor / Michael Khachay ; Panos Pardalos ; Yury Kochetov. Springer-Verlag GmbH and Co. KG, 2019. pp. 279-294 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

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

}

RIS

TY - GEN

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

AU - van Bevern, René

AU - Fluschnik, Till

AU - Tsidulko, Oxana Yu

PY - 2019/1/1

Y1 - 2019/1/1

N2 - 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.

AB - 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.

KW - Eulerian extension

KW - Lossy kernelization

KW - Parameterized complexity

KW - EULERIAN EXTENSION

KW - APPROXIMATION

KW - BOUNDS

UR - http://www.scopus.com/inward/record.url?scp=85067648703&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-22629-9_20

DO - 10.1007/978-3-030-22629-9_20

M3 - Conference contribution

AN - SCOPUS:85067648703

SN - 9783030226282

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 279

EP - 294

BT - Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Proceedings

A2 - Khachay, Michael

A2 - Pardalos, Panos

A2 - Kochetov, Yury

PB - Springer-Verlag GmbH and Co. KG

T2 - 18th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2019

Y2 - 8 July 2019 through 12 July 2019

ER -

ID: 20640923