文章基本信息

标题：A (k+3)/2-approximation algorithm for monotone submodular k-set packing and general k-exchange systems
本地全文：下载
作者：Justin Ward
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2012
卷号：14
页码：42-53
DOI：10.4230/LIPIcs.STACS.2012.42
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We consider the monotone submodular k-set packing problem in the context of the more general problem of maximizing a monotone submodular function in a k-exchange system. These systems, introduced by Feldman et al. [Feldman,2011], generalize the matroid k-parity problem in a wide class of matroids and capture many other combinatorial optimization problems. We give a deterministic, non-oblivious local search algorithm that attains an approximation ratio of (k + 3)/2 + epsilon for the problem of maximizing a monotone submodular function in a k-exchange system, improving on the best known result of k+epsilon, and answering an open question posed by Feldman et al.
关键词：k-set packing; k-exchange systems; submodular maximization; local search; approximation algorithms