moteur de recherche

Séminaire Algo - René van Bevern
Séminaire Algo - René van Bevern
24-Nov-2020 14:00
Age: 57 days

René van Bevern

On approximate data reduction for the Rural Postman Problem

Lieu : en ligne

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

<- Back to: Accueil