The NP-hard Multiple Hitting Set problem is finding a minimum-cardinality set intersecting each of the sets in a given input collection a given number of times. Generalizing a well-known data reduction algorithm due to Weihe, we show a problem kernel for Multiple Hitting Set parameterized by the Dilworth number, a graph parameter introduced by Foldes and Hammer in 1978 yet seemingly so far unexplored in the context of parameterized complexity theory. Using matrix multiplication, we speed up the algorithm to quadratic sequential time and logarithmic parallel time. We experimentally evaluate our algorithms. By implementing our algorithm on GPUs, we show the feasability of realizing kernelization algorithms on SIMD (Single Instruction, Multiple Date) architectures.


翻译:NP-hard 多重打击设置问题正在找到一个最小心电图集, 将每个数据集在给定的输入收藏中互相交叉一个特定次数。 由于 Weihe 将已知的数据减少算法普遍化, 我们用 Dilworth 编号来显示多击集参数的问题内核, 这是Foldes 和 Hammer 于1978年推出的图形参数, 但是在参数化复杂理论中似乎至今尚未探索 。 使用矩阵乘法, 我们加速算法, 以进行二次相继时间和对数平行时间 。 我们实验性地评估我们的算法。 通过在 GPUs 上应用我们的算法, 我们展示了在 SIMD( 单个指令、 多日期) 结构上实现内核化算法的可能性 。

0
下载
关闭预览

相关内容

简称 哈工大,创建于1920年,是C9联盟成员之一,国内工科顶尖高校。1999年成为首批九所985工程院校之一,校训是“规格严格,功夫到家”。
【Google】平滑对抗训练,Smooth Adversarial Training
专知会员服务
48+阅读 · 2020年7月4日
Python计算导论,560页pdf,Introduction to Computing Using Python
专知会员服务
72+阅读 · 2020年5月5日
100+篇《自监督学习(Self-Supervised Learning)》论文最新合集
专知会员服务
163+阅读 · 2020年3月18日
2019年机器学习框架回顾
专知会员服务
35+阅读 · 2019年10月11日
TensorFlow 2.0 分布式训练
TensorFlow
8+阅读 · 2020年1月19日
强化学习三篇论文 避免遗忘等
CreateAMind
19+阅读 · 2019年5月24日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
【SIGIR2018】五篇对抗训练文章
专知
12+阅读 · 2018年7月9日
carla无人驾驶模拟中文项目 carla_simulator_Chinese
CreateAMind
3+阅读 · 2018年1月30日
gan生成图像at 1024² 的 代码 论文
CreateAMind
4+阅读 · 2017年10月31日
Adversarial Variational Bayes: Unifying VAE and GAN 代码
CreateAMind
7+阅读 · 2017年10月4日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
0+阅读 · 2021年11月2日
Arxiv
0+阅读 · 2021年10月30日
VIP会员
相关资讯
TensorFlow 2.0 分布式训练
TensorFlow
8+阅读 · 2020年1月19日
强化学习三篇论文 避免遗忘等
CreateAMind
19+阅读 · 2019年5月24日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
【SIGIR2018】五篇对抗训练文章
专知
12+阅读 · 2018年7月9日
carla无人驾驶模拟中文项目 carla_simulator_Chinese
CreateAMind
3+阅读 · 2018年1月30日
gan生成图像at 1024² 的 代码 论文
CreateAMind
4+阅读 · 2017年10月31日
Adversarial Variational Bayes: Unifying VAE and GAN 代码
CreateAMind
7+阅读 · 2017年10月4日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员