首页> 外文会议>International Integer Programming and Combinatorial Optimization(IPCO) Conference; 20070625-27; Ithaca,NY(US) >Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)
【24h】

Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)

机译:最大化受拟阵约束的子模集函数(扩展摘要)

获取原文
获取原文并翻译 | 示例

摘要

Let f : 2~N → R~+ be a non-decreasing submodular set function, and let (N, I) be a matroid. We consider the problem max s∈x f(S). It is known that the greedy algorithm yields a 1/2-approximation [9] for this problem. It is also known, via a reduction from the max-k-cover problem, that there is no (1 - 1/e + ε)-approximation for any constant ε > 0, unless P = NP [6]. In this paper, we improve the 1/2-approximation to a (1 - 1/e)-approximation, when / is a sum of weighted rank functions of matroids. This class of functions captures a number of interesting problems including set coverage type problems. Our main tools are the pipage rounding technique of Ageev and Sviridenko [1] and a probabilistic lemma on monotone submodular functions that might be of independent interest. We show that the generalized assignment problem (GAP) is a special case of our problem; although the reduction requires |N| to be exponential in the original problem size, we are able to interpret the recent (1 - 1/e)-approximation for GAP by Fleischer et al. [10] in our framework. This enables us to obtain a (1 - 1/e)-approximation for variants of GAP with more complex constraints.
机译:令f:2〜N→R〜+为非递减子模集函数,令(N,I)为拟阵。我们考虑问题maxs∈xf(S)。众所周知,贪婪算法针对此问题得出1/2近似值[9]。通过减少max-k-cover问题,还已知对于任何常数ε> 0,都没有(1-1 / e +ε)逼近,除非P = NP [6]。在本文中,当/是拟阵的加权秩函数之和时,我们将1/2近似改进为(1/1 / e)近似。此类功能捕获了许多有趣的问题,包括集合覆盖类型问题。我们的主要工具是Ageev和Sviridenko [1]的pipage四舍五入技术,以及关于单调子模函数的概率引理,这些引理可能是独立的。我们证明了广义分配问题(GAP)是我们问题的特例;尽管减少需要| N |为了使原始问题的大小成指数,我们可以解释Fleischer等人最近的GAP(1 / e)逼近。 [10]在我们的框架中。这使我们可以获得具有更复杂约束的GAP变量的(1-1 / e)逼近。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号