On approximate data reduction for the Rural Postman Problem: Theory and experiments

Результат исследования: Научные публикации в периодических изданияхстатьярецензирование

4 Цитирования (Scopus)


Given an undirected graph with edge weights and a subset R of its edges, the Rural Postman Problem (RPP) is to find a closed walk of minimum total weight containing all edges of R. We prove that RPP is WK[1]-complete parameterized by the number and weight d of edges traversed additionally to the required ones. Thus RPP instances cannot be polynomial-time compressed to instances of size polynomial in d unless the polynomial-time hierarchy collapses. 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(n3) 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 experimentally evaluate it on wide-spread benchmark data sets as well as on two real snow plowing instances from Berlin. We also make first steps toward a PSAKS for the parameter c.

Язык оригиналаанглийский
Номер статьиe21985
Страницы (с-по)485-508
Число страниц24
Номер выпуска4
Ранняя дата в режиме онлайн6 окт 2020
СостояниеОпубликовано - 1 дек 2020

Fingerprint Подробные сведения о темах исследования «On approximate data reduction for the Rural Postman Problem: Theory and experiments». Вместе они формируют уникальный семантический отпечаток (fingerprint).