We investigate computational problems involving large weights through the lens of kernelization, which is a framework of polynomial-time preprocessing aimed at compressing the instance size. Our main focus is the weighted Clique problem, where we are given an edge-weighted graph and the goal is to detect a clique of total weight equal to a prescribed value. We show that the weighted variant, parameterized by the number of vertices $n$, is significantly harder than the unweighted problem by presenting an $O(n^{3 - \varepsilon})$ lower bound on the size of the kernel, under the assumption that NP $\not \subseteq$ coNP/poly. This lower bound is essentially tight: we show that we can reduce the problem to the case with weights bounded by $2^{O(n)}$, which yields a randomized kernel of $O(n^3)$ bits. We generalize these results to the weighted $d$-Uniform Hyperclique problem, Subset Sum, and weighted variants of Boolean Constraint Satisfaction Problems (CSPs). We also study weighted minimization problems and show that weight compression is easier when we only want to preserve the collection of optimal solutions. Namely, we show that for node-weighted Vertex Cover on bipartite graphs it is possible to maintain the set of optimal solutions using integer weights from the range $[1, n]$, but if we want to maintain the ordering of the weights of all inclusion-minimal solutions, then weights as large as $2^{\Omega(n)}$ are necessary.


翻译:我们通过内核化的透镜来调查涉及大重量的计算问题。 内核化是一个多元时预处理框架, 旨在压缩实例大小。 我们的主要焦点是加权 clique 问题, 给我们一个边加权图, 目标是检测一个总重量与规定值相等的球状。 我们显示, 加权变量, 以螺旋数为参数, 比未加权问题要困难得多得多 。 我们将这些结果概括为美元( n% 3 -\varepsilon} ) 内核重量的比值低, 假设其重量的比值是 NP $\ not\ subseqeq$ comple/polear。 这个更下限基本上很紧 : 我们显示, 以2 ⁇ (n) $ min) 来减少总重量的总重量的球质。 我们将这些结果概括为美元- Uncial- clocial 的比值解决方案的比值, 我们想要将所有 美元 的比值 的比值 继续 。 将 MI 的比值 问题, suse Sum sult sult 和 等 重量的比值变值的比值的比值 。 当 我们的比值 最重的比值 的比值的比值

0
下载
关闭预览

相关内容

专知会员服务
38+阅读 · 2021年8月20日
专知会员服务
50+阅读 · 2020年12月14日
【清华大学】图随机神经网络,Graph Random Neural Networks
专知会员服务
154+阅读 · 2020年5月26日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
人工智能 | 国际会议信息10条
Call4Papers
5+阅读 · 2018年12月18日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
神经网络学习率设置
机器学习研究会
4+阅读 · 2018年3月3日
分布式TensorFlow入门指南
机器学习研究会
4+阅读 · 2017年11月28日
计算机视觉近一年进展综述
机器学习研究会
9+阅读 · 2017年11月25日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Arxiv
0+阅读 · 2021年9月7日
Arxiv
0+阅读 · 2021年9月6日
Arxiv
0+阅读 · 2021年9月4日
Arxiv
0+阅读 · 2021年9月3日
VIP会员
相关VIP内容
专知会员服务
38+阅读 · 2021年8月20日
专知会员服务
50+阅读 · 2020年12月14日
【清华大学】图随机神经网络,Graph Random Neural Networks
专知会员服务
154+阅读 · 2020年5月26日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
人工智能 | 国际会议信息10条
Call4Papers
5+阅读 · 2018年12月18日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
神经网络学习率设置
机器学习研究会
4+阅读 · 2018年3月3日
分布式TensorFlow入门指南
机器学习研究会
4+阅读 · 2017年11月28日
计算机视觉近一年进展综述
机器学习研究会
9+阅读 · 2017年11月25日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Top
微信扫码咨询专知VIP会员