algorithm - 顶点权重可能为负时的最大权重独立集逼近算法

Question

最大权重独立集的逼近算法有很多。但他们中的大多数假设非负权重。是否有任何算法适用于可能的负权重？

Answer 1

忽略负权顶点。考虑任何包含负权顶点的独立集合。如果您删除该顶点，则结果集仍然是一个独立集，但您增加了它的总权重。