




















The classical problem of maximizing a submodular function under a matroid constraint is considered. Defining a new measure for the increments made by the greedy algorithm at each step, called the discriminant, improved approximation ratio guarantees are derived for the greedy algorithm. At each step, discriminant measures the multiplicative gap in the incremental valuation between the item chosen by the greedy algorithm and the largest potential incremental valuation for eligible items not selected by it. The new guarantee subsumes all the previous known results for the greedy algorithm, including the curvature based ones, and the derived guarantees are shown to be tight via constructing specific instances. More refined approximation guarantee is derived for a special case called the submodular welfare maximization/partition problem that is also tight, for both the offline and the online case.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。