论文标题
稀疏ILP和HyperGraph Multi-Taking/Multi-Cover问题的更快算法
Faster Algorithms for Sparse ILP and Hypergraph Multi-Packing/Multi-Cover Problems
论文作者
论文摘要
在我们的论文中，我们考虑以下一般问题：检查可行性，计算可行解决方案的数量，找到最佳解决方案，并计算$ p \ cap z^n $中最佳解决方案的数量，假设$ p $是$ p $，是由系统$ a x \ leq b $或$ ax = b $ a x = b，\ a x = b，\，x \ geq 0 $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a我们为这些问题开发了算法，这些问题表现优于最先进的ILP状态并在具有有限元素的稀疏实例上计算算法。 我们使用已知的新方法来开发用于边缘/顶点多包装/多包覆盖问题的新指数算法。该框架由许多不同的问题组成，例如稳定的多设置，顶点多封面，主导多设置，设置多封面，多组的多组覆盖和超图多匹配问题，这些问题是标准稳定集，顶点稳定集，顶点盖子盖，统治，设置，设置，设置和最大匹配问题的自然概括。
In our paper, we consider the following general problems: check feasibility, count the number of feasible solutions, find an optimal solution, and count the number of optimal solutions in $P \cap Z^n$, assuming that $P$ is a polyhedron, defined by systems $A x \leq b$ or $Ax = b,\, x \geq 0$ with a sparse matrix $A$. We develop algorithms for these problems that outperform state of the art ILP and counting algorithms on sparse instances with bounded elements. We use known and new methods to develop new exponential algorithms for Edge/Vertex Multi-Packing/Multi-Cover Problems on graphs and hypergraphs. This framework consists of many different problems, such as the Stable Multi-set, Vertex Multi-cover, Dominating Multi-set, Set Multi-cover, Multi-set Multi-cover, and Hypergraph Multi-matching problems, which are natural generalizations of the standard Stable Set, Vertex Cover, Dominating Set, Set Cover, and Maximal Matching problems.
