论文标题
平行体系结构上离散优化问题的内核化
Kernelization of Discrete Optimization Problems on Parallel Architectures
论文作者
论文摘要
现有的标准求解器可以解决离散优化问题。但是，实际上，将它们直接应用于此类问题的典型大型输入空间并不常见。相反，将输入进行预处理以寻求简化并提取问题空间的核心子集，这称为内核。此预处理过程在参数化复杂性理论的背景下是核心化。 在本文中，我实现了某些内核化算法的并行版本并评估其性能。内核化算法的性能是通过输出内核的大小或计算内核所需的时间来测量的。有时，内核与原始输入相同，因此希望尽快知道这一点。问题范围仅限于特定类型的离散优化问题，该问题是K-Clique问题的一种版本，其中给定图的节点使用K颜色在法律上进行了预彩。 最终评估表明，对于这些算法，我的并行实现效率提高了50％以上。这不仅是在速度方面实现的，而且还可以产生较小的内核。
There are existing standard solvers for tackling discrete optimization problems. However, in practice, it is uncommon to apply them directly to the large input space typical of this class of problems. Rather, the input is preprocessed to look for simplifications and to extract the core subset of the problem space, which is called the Kernel. This pre-processing procedure is known in the context of parameterized complexity theory as Kernelization. In this thesis, I implement parallel versions of some Kernelization algorithms and evaluate their performance. The performance of Kernelization algorithms is measured either by the size of the output Kernel or by the time it takes to compute the kernel. Sometimes the Kernel is the same as the original input, so it is desirable to know this, as soon as possible. The problem scope is limited to a particular type of discrete optimisation problem which is a version of the K-clique problem in which nodes of the given graph are pre-coloured legally using k colours. The final evaluation shows that my parallel implementations achieve over 50% improvement in efficiency for at least one of these algorithms. This is attained not just in terms of speed, but it is also able to produce a smaller kernel.
