On approximate data reduction for the Rural Postman Problem: Theory and experiments
On approximate data reduction for the Rural Postman Problem: Theory and experiments
复制标题
农村邮递员问题的近似数据约简：理论与实验
DOI：
10.1002/net.21985
复制
发表时间：
2020
期刊：
影响因子：
2.1
通讯作者：
O. Y. Tsidulko
中科院分区：
文献类型：
--
作者：
R. van Bevern;T. Fluschnik;O. Y. Tsidulko
给定一个具有边权的无向图及其边子集R，乡村邮递员问题（RPP）是寻找一个包含R的所有边的总权最小的闭行走。我们证明了RPP是WK[1]-完全的，由除了所需的边之外遍历的边的数量和权重参数化。因此，RPP实例不能被多项式时间压缩到大小为多项式inds的实例，除非多项式时间层次结构崩溃。与此相反，设b ≤ 2d表示与R的奇数条边关联的顶点数，c ≤ d表示由R中的边形成的连通分支数，我们证明了如何在O（n3）时间内将任何RPP实例I约化为具有2b+O（c/n）个顶点的RPP实例I ′，使得I ′的任何α-近似解给出I的α（1 + n）-近似解，其中α≥ 1且n> 0。也就是说，我们提供了一个多项式大小的近似核化方案（PSAKS）。我们在广泛的基准数据集以及来自柏林的两个真实的扫雪实例上进行了实验评估。我们还为参数c的PSAKS迈出了第一步。
Given an undirected graph with edge weights and a subsetRof its edges, the Rural Postman Problem (RPP) is to find a closed walk of minimum total weight containing all edges ofR. We prove that RPP is WK[1]‐complete parameterized by the number and weightdof edges traversed additionally to the required ones. Thus RPP instances cannot be polynomial‐time compressed to instances of size polynomial indunless the polynomial‐time hierarchy collapses. In contrast, denoting byb≤ 2dthe number of vertices incident to an odd number of edges ofRand byc≤dthe number of connected components formed by the edges inR, we show how to reduce any RPP instanceIto an RPP instanceI′with 2b+O(c/ϵ) vertices inO(n3) time so that anyα‐approximate solution forI′gives anα(1 +ϵ)‐approximate solution forI, 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 parameterc.
登录
查看更多内容
混合多风电容弧路由问题的参数化近似算法：理论与实验
影响因子：
2.1
作者：
R. van Bevern;C. Komusiewicz;und M. Sorge
通讯作者：
und M. Sorge
用于命中子图的有损内核
DOI：
--
发表时间：
2017
期刊：
International Symposium on Mathematical Foundations of Computer Science
影响因子：
--
作者：
E. Eiben;D. Hermelin;M. Ramanujan
通讯作者：
M. Ramanujan
计算图的最佳最小割分区及其在路由问题中的应用
影响因子：
1.1
作者：
G. Reinelt;D. Theis;K. Wenger
通讯作者：
K. Wenger
影响因子：
2.1
作者：
K. Jansen
通讯作者：
K. Jansen
线性时间和空间中 d-Hitting 集的最优大小问题核
影响因子：
0.5
作者：
René van Bevern;P. Smirnov
通讯作者：
P. Smirnov