具有一般成本约束的子集选择

本文考虑具有单调目标函数和单调代价约束的子集选择问题，从而放宽了先前研究的子模性质。 我们首先表明，广义贪婪算法的近似率为2（1 1 e）（其中，为次模数比）。 然后提出POMC，这是一种随时随地的迭代方法，与广义的贪婪算法相比，它可以利用更多的时间来找到更好的解决方案。 我们证明，POMC可以获得与广义贪婪算法相同的一般逼近保证，但是可以在情况和应用中实现更好的解决方案。