文章基本信息

标题：Towards Nearly-Linear Time Algorithms for Submodular Maximization with a Matroid Constraint
本地全文：下载
作者：Alina Ene ; Huy L. Nguyen
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：132
页码：1-14
DOI：10.4230/LIPIcs.ICALP.2019.54
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We consider fast algorithms for monotone submodular maximization subject to a matroid constraint. We assume that the matroid is given as input in an explicit form, and the goal is to obtain the best possible running times for important matroids. We develop a new algorithm for a general matroid constraint with a 1 - 1/e - epsilon approximation that achieves a fast running time provided we have a fast data structure for maintaining an approximately maximum weight base in the matroid through a sequence of decrease weight operations. We construct such data structures for graphic matroids and partition matroids, and we obtain the first algorithms for these classes of matroids that achieve a nearly-optimal, 1 - 1/e - epsilon approximation, using a nearly-linear number of function evaluations and arithmetic operations.
关键词：submodular maximization; matroid constraints; fast running times