Reducing a Target Interval to a Few Exact Queries
Reducing a Target Interval to a Few Exact Queries
复制标题
将目标间隔减少到几个精确查询
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
R. V. D. Zwaan
中科院分区：
文献类型：
--
作者：
Jesper Nederlof;E. J. V. Leeuwen;R. V. D. Zwaan
许多涉及权重的组合问题可以被公式化为所谓的范围问题。也就是说，他们的输入包括一个宇宙u，一个（简洁表示）集合族mathcal{f} subseteq 2^{u}f？2 u mathcal{f} subseteq 2^{u}，权重函数？：u？{1，.，n}和整数0？=？l？=？u？8.那么问题是决定是否有一个x在mathcal{f}x？fx在mathcal{f}中使得l？=？是吗？x？(e)?=?联合这类问题的著名例子包括背包、子集和、最大匹配和旅行推销员。在本文中，我们开发了一种通用的方法，将范围问题转化为一个确切的问题（即范围的问题，l？u）。我们表明，我们的方法有几个有趣的应用程序在精确的指数算法和参数化的复杂性，即：在精确的指数算法，我们提出了新的见解子集和背包是否有效率的算法在时间和空间。特别是，我们表明，时间和空间复杂性的子集和背包是等价的一个小的多项式因子的输入大小。我们还给出了一个算法，有效地解决背包稀疏的情况下，在空间和时间。在参数化的复杂性，我们提出了第一个核化结果的几个著名的问题的加权变体。特别地，我们证明了顶点覆盖和控制集、旅行商和背包的加权变体都允许多项式随机图灵核，|u|.奇怪的是，我们的方法依赖于一种在近似算法中更常见的技术。
Many combinatorial problems involving weights can be formulated as a so-called ranged problem. That is, their input consists of a universe u, a (succinctly-represented) set family mathcal{f} subseteq 2^{u}f?2 u mathcal{f} subseteq 2^{u}, a weight function ?:u?{1,…,n}, and integers 0?=?l?=?u?=?8. Then the problem is to decide whether there is an x in mathcal{f}x?fx in mathcal{f} such that l?=? e?x ?(e)?=?u. Well-known examples of such problems include knapsack, subset sum, maximum matching, and traveling salesman. In this paper, we develop a generic method to transform a ranged problem into an exact problem (i.e. A ranged problem for which l?=?u). We show that our method has several intriguing applications in exact exponential algorithms and parameterized complexity, namely: , in exact exponential algorithms, we present new insight into whether subset sum and knapsack have efficient algorithms in both time and space. In particular, we show that the time and space complexity of subset sum and knapsack are equivalent up to a small polynomial factor in the input size. We also give an algorithm that solves sparse instances of knapsack efficiently in terms of space and time. In parameterized complexity, we present the first kernelization results on weighted variants of several well-known problems. In particular, we show that weighted variants of vertex cover and dominating set, traveling salesman, and knapsack all admit polynomial randomized turing kernels when parameterized by |u|. Curiously, our method relies on a technique more commonly found in approximation algorithms.