选择k个子集
我在尝试分类算法时遇到了以下算法问题。元素被分类为多层次结构，我理解为具有单根的偏序集。我必须解决以下问题，它看起来很像设置封面问题。
我在此处上传了我的 Latex 问题描述。
设计一种满足 1 & 的近似算法。 2 非常简单，只需从 G 的顶点开始并“向上走”或从根部开始并“向下走”。假设您从根开始，迭代扩展顶点，然后删除不必要的顶点，直到至少有 k 个子格子。近似界限取决于顶点的子级数量，这对于我的应用程序来说是可以的。
有谁知道这个问题是否有正确的名称，或者问题的树版本？我有兴趣知道这个问题是否是 NP 难问题，也许有人有一个好的 NP 难问题的想法来减少或有一个多项式算法来解决该问题。如果您两者都有，请收集您的百万美元价格。 ;)
I ran into the following algorithmic problem while experimenting with classification algorithms. Elements are classified into a polyhierarchy, what I understand to be a poset with a single root. I have to solve the following problem, which looks a lot like the set cover problem.
I uploaded my Latex-ed problem description here.
Devising an approximation algorithm that satisfies 1 & 2 is quite easy, just start at the vertices of G and "walk up" or start at the root and "walk down". Say you start at the root, iteratively expand vertexes and then remove unnecessary vertices until you have at least k sub-lattices. The approximation bound depends on the number of children of a vertex, which is OK for my application.
Does anyone know if this problem has a proper name, or maybe the tree-version of the problem? I would be interested to find out if this problem is NP-hard, maybe someone has ideas for a good NP-hard problem to reduce or has a polynomial algorithm to solve the problem. If you have both collect your million dollar price. ;)
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
DAG 版本是通过（击鼓）从布景封面上减少来实现的。设置 k = 2 并执行显而易见的操作：条件 (2) 阻止我们求根。 （请注意，由于下界 k，（3）实际上并不意味着（2）。）
树版本是串并偏序集版本的特例，可以在多项式时间内精确求解。这是一个给出多项式 p(x) 的递归公式，其中 xn 的系数是基数 n 的覆盖次数。
要覆盖的单个顶点：p(x) = x。
其他顶点：p(x) = 1 + x。
并行组合，其中 q 和 r 是两个偏序集的多项式：q(x) r(x)。
系列组合，其中 q 是顶部偏序集的多项式，r 是底部偏序集的多项式： 如果顶部偏序集不包含要覆盖的顶点，则 p(x) = (q(x) - 1) + r(x)；否则，p(x) = q(x)。
The DAG version is hard by (drum roll) a reduction from set cover. Set k = 2 and do the obvious: condition (2) prevents us from taking the root. (Note that (3) doesn't actually imply (2) because of the lower bound k.)
The tree version is a special case of the series-parallel poset version, which can be solved exactly in polynomial time. Here's a recursive formula that gives a polynomial p(x) where the coefficient of xn is the number of covers of cardinality n.
Single vertex to be covered: p(x) = x.
Other vertex: p(x) = 1 + x.
Parallel composition, where q and r are the polynomials for the two posets: q(x) r(x).
Series composition, where q is the polynomial for the top poset and r, for the bottom: If the top poset contains no vertices to be covered, then p(x) = (q(x) - 1) + r(x); otherwise, p(x) = q(x).