On Polynomial Kernels for Integer Linear Programs: Covering, Packing and Feasibility
On Polynomial Kernels for Integer Linear Programs: Covering, Packing and Feasibility
复制标题
整数线性规划的多项式核：覆盖、打包和可行性
DOI：
10.1007/978-3-642-40450-4_55
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Stefan Kratsch
中科院分区：
文献类型：
--
作者：
Stefan Kratsch
研究了整数线性规划可行性判定问题的多项式核的存在性，以及整数线性规划复盖和填充问题的解的存在性。我们的主要研究结果如下：首先，我们证明了当用变量数和约束数来参数化时，该ilp可行性问题不允许多项式核化，除非NP任任coNP/poly。这扩展到每个约束的有限变量度和有限变量数的限制情况，以及覆盖和包装ilp。其次，我们给出了coverilp问题的多项式核化，求出ax≥bwithcTx≤k，参数化byk，当其行稀疏时的解；这推广了已知的0/1变量和系数的特殊情况的多项式核化（d-Hitting Set）。
We study the existence of polynomial kernels for the problem of deciding feasibility of integer linear programs (ILPs), and for finding good solutions for covering and packing ILPs. Our main results are as follows: First, we show that theILP Feasibilityproblem admits no polynomial kernelization when parameterized by both the number of variables and the number of constraints, unless NP ⊆ coNP/poly. This extends to the restricted cases of bounded variable degree and bounded number of variables per constraint, and to covering and packing ILPs. Second, we give a polynomial kernelization for theCover ILPproblem, asking for a solution toAx≥bwithcTx≤k, parameterized byk, whenAis row-sparse; this generalizes a known polynomial kernelization for the special case with 0/1-variables and coefficients (d-Hitting Set).
将目标间隔减少到几个精确查询
DOI：
--
发表时间：
2012
期刊：
International Symposium on Mathematical Foundations of Computer Science
影响因子：
--
作者：
Jesper Nederlof;E. J. V. Leeuwen;R. V. D. Zwaan
通讯作者：
R. V. D. Zwaan
重新审视顶点覆盖核化
影响因子：
0.5
作者：
B. Jansen;H. Bodlaender
通讯作者：
H. Bodlaender