PaperlayerView exact revision on arXiv

Source-linked AI summary

Constrained Non-Monotone Submodular Maximization: Offline and Secretary Algorithms

Anupam Gupta, Aaron Roth, Grant Schoenebeck, Kunal Talwar

arXiv:1003.1517v2cs.DScs.GT

TL;DR

The paper studies non-monotone submodular maximization under constraints, where prior methods for matroid intersections could require runtimes exponential in the number of constraints. It adapts greedy algorithms to p-independence systems and knapsack constraints, then extends the approach to secretary settings. The resulting guarantees include O(p) offline approximation, constant-factor guarantees for knapsack, cardinality, and partition constraints, and O(log k) for rank-k matroids, with faster runtimes but weaker constants for some constant-p cases.

  • Problem

    Non-monotone constrained submodular maximization was less understood, and prior matroid-intersection algorithms could be polynomial-time only for constantly many matroids.

  • Method

    The paper adapts greedy algorithms from monotone maximization and uses them to design offline and secretary algorithms for non-monotone objectives.

  • Results

    O(p)-approximation is obtained for p-independence systems, constant-factor approximations for knapsack, cardinality, and partition constraints, and O(log k) approximation for rank-k matroids.

  • Takeaways & Limitations

    Greedy-based methods provide polynomial dependence on p offline and enable the first secretary algorithms for non-monotone submodular objectives in the stated constrained settings.

  • Takeaways & Limitations

    For constant p, the algorithms have worse approximation factors than some prior results, and improving those factors likely requires more than parameter tuning.

Abstract

from arXiv · show

Constrained submodular maximization problems have long been studied, with near-optimal results known under a variety of constraints when the submodular function is monotone. The case of non-monotone submodular maximization is less understood: the first approximation algorithms even for the unconstrainted setting were given by Feige et al. (FOCS '07). More recently, Lee et al. (STOC '09, APPROX '09) show how to approximately maximize non-monotone submodular functions when the constraints are given by the intersection of p matroid constraints; their algorithm is based on local-search procedures that consider p-swaps, and hence the running time may be n^Omega(p), implying their algorithm is polynomial-time only for constantly many matroids. In this paper, we give algorithms that work for p-independence systems (which generalize constraints given by the intersection of p matroids), where the running time is poly(n,p). Our algorithm essentially reduces the non-monotone maximization problem to multiple runs of the greedy algorithm previously used in the monotone case. Our idea of using existing algorithms for monotone functions to solve the non-monotone case also works for maximizing a submodular function with respect to a knapsack constraint: we get a simple greedy-based constant-factor approximation for this problem. With these simpler algorithms, we are able to adapt our approach to constrained non-monotone submodular maximization to the (online) secretary setting, where elements arrive one at a time in random order, and the algorithm must make irrevocable decisions about whether or not to select each element as it arrives. We give constant approximations in this secretary setting when the algorithm is constrained subject to a uniform matroid or a partition matroid, and give an O(log k) approximation when it is constrained by a general matroid of rank k.

1 Introduction

The paper adapts greedy methods for non-monotone submodular maximization, extending offline guarantees to broader constraints and enabling secretary algorithms with irrevocable online decisions. It achieves polynomial dependence on p for p-independence systems, constant-factor guarantees for knapsack, cardinality, and partition constraints, and an O(log k) guarantee for rank-k matroids, while trading approximation quality for faster runtimes.

  • Offline algorithms: The paper adapts algorithms successful for monotone submodular maximization to non-monotone, non-negative objectives under varied constraints.Its central offline idea uses greedy approaches rather than the prior local-search framework.
  • Offline algorithms: O(p)-approximation applies to p-independence systems, with runtime polynomial in p and the first polynomial-time algorithms for non-constant p.This generalizes prior results for intersections of p matroids, which form a subclass of p-independence systems.
  • Offline algorithms: A constant-factor approximation is obtained for non-monotone submodular maximization under one knapsack constraint using a greedy-based algorithm.The method provides an alternative to earlier LP-rounding-based approaches for related knapsack constraints.
  • Secretary algorithms: In the secretary setting, elements arrive in random order and selection decisions are irrevocable, creating complications because marginal values depend on earlier choices.The paper applies its simpler greedy-based ideas to this online setting.
  • Secretary algorithms: O(1)-approximation is achieved for cardinality and partition matroid constraints, while O(log k)-approximation is achieved for arbitrary rank-k matroids.The secretary algorithms for the first two settings are described as simple and efficient, and the general-matroid bound matches the known linear matroid-secretary bound.
  • Limitations and trade-offs: The paper trades worse constant approximation factors for exponential runtime improvements over prior algorithms for constant numbers of matroid constraints.Its runtime is linear in p, whereas prior methods used runtimes exponential in p; matching earlier constant-p ratios remains open.
  • Main ideas: The offline approach reduces non-monotone maximization to repeated greedy-style procedures and, when needed, unconstrained maximization on a greedy-produced set.The analysis compares f(S) with f(S ∪ C*) and considers either extracting value from S or rerunning the procedure outside S.

2 Submodular Maximization subject to a Cardinality Constraint

The section adapts greedy cardinality-constrained maximization to non-monotone submodular functions, using multiple candidate sets and an unconstrained approximation algorithm. It obtains a (4 + α)-approximation, including a 6.5-approximation when α = 2.5.

  • Greedy algorithm: The greedy algorithm repeatedly selects the feasible element with maximum marginal value until k elements are chosen.For non-monotone functions, the algorithm may continue adding elements with negative marginal gain.
  • Limitation: The greedy bound is existentially tight for cardinality constraints when the function is the cardinality function and the compared sets are disjoint.The section notes that this prevents improving the relevant factor beyond 1/2 in that example.
  • Guarantee: (4 + α)-approximation is achieved by the Submod-Max-Cardinality algorithm.The algorithm uses the same multi-pass structure as prior work but replaces local-search analysis with greedy analysis.
  • Analysis: The analysis combines greedy bounds with an α-approximation for unconstrained non-monotone submodular maximization.If the greedy set overlaps the optimum substantially, the unconstrained algorithm extracts value; otherwise, submodularity bounds the candidate sets.
  • Guarantee: 6.5-approximation follows from the known unconstrained guarantee α = 2.5.This is weaker than several earlier cardinality results but uses a faster approach whose improvement extends to other settings.

3 Fast Algorithms for p-Systems and Knapsacks

The section develops greedy-based algorithms for non-monotone submodular maximization over p-independence systems and knapsack constraints. It obtains an O(p)-type guarantee for p-systems and a constant-factor guarantee for knapsacks, with polynomial dependence on p.

  • p-independence systems: p-independence systems generalize intersections of p matroids, while retaining the hereditary and basis-rank structure used by the analysis.The paper explicitly notes that every intersection of p matroids is a p-independent system, but not conversely.
  • p-independence systems: The greedy algorithm builds an independent set by repeatedly choosing the feasible element with maximum marginal value.For non-monotone objectives, it continues adding elements even when their marginal gains are negative.
  • p-independence systems: (1 + α)(p + 2 + 1/p)-approximation is obtained for non-monotone maximization over a p-independence system.Here α is the approximation guarantee for unconstrained non-monotone submodular maximization.
  • p-independence systems: The resulting p-system algorithm runs in time polynomial in p, unlike prior local-search methods whose running time could be exponential in p.The paper identifies this as the first polynomial-time approach when p is super-constant, while noting constant-factor differences for small p.
  • Knapsack constraints: A tight cardinality example shows that the corresponding factor cannot generally be improved beyond 1/2.This bound is presented as a limitation relevant to the knapsack-related analysis.
  • Knapsack constraints: (4 + α)-approximation is achieved for non-monotone submodular maximization under a knapsack constraint.The method modifies a greedy algorithm with partial enumeration that was previously used for monotone knapsack maximization.

4 Constrained Submodular Maximization in the Secretary Setting

The paper adapts greedy-style algorithms for non-monotone submodular maximization to secretary settings with irrevocable online decisions. It obtains constant-factor approximations for cardinality and partition-matroid constraints, and an O(log k) approximation for rank-k general matroids.

  • Overview: The secretary setting requires irrevocable selections from elements arriving online in random order.The algorithms are designed to avoid offline local search and operate through online decisions.
  • Lower bound: No secretary algorithm can approximate cardinality-constrained submodular maximization within a factor better than a universal constant greater than 1.This information-theoretic lower bound is independent of k and ignores computational constraints.
  • Cardinality constraint: The cardinality algorithm uses threshold selection, random sampling, and a uniformly random choice among three constructed solutions.The threshold is set using OPT in the advice-taking version, while sampling estimates OPT for the secretary model.
  • Cardinality constraint: OPT/21 is the expected value guaranteed by the advice-taking cardinality algorithm.The guarantee follows after setting τ = OPT/7k and using FMV4 in the fourth step.
  • Cardinality constraint: O(1) is the approximation factor for cardinality-constrained submodular maximization in the secretary setting.The secretary algorithm estimates OPT from the first half of the elements and then runs the advice-taking algorithm.
  • Partition matroid: (3 + 6e) is the approximation factor for contiguous partition segments.For fully random element order, the analysis yields an O(1) approximation under a partition matroid.
  • General matroid: O(log k) is the approximation factor for secretary maximization under a rank-k general matroid.The proof separates cases according to whether the highest-value element contributes more than half of OPT.

A Proof of Main Lemma for p-Systems

The proof establishes the main p-system greedy lemma by partitioning an arbitrary independent comparison set according to when greedy loses feasibility. Submodularity and the p-independence property then relate these parts to greedy’s marginal gains.

  • Proof setup: The greedy solution is represented by elements e1 through ek with non-increasing marginal gains δi.The gains satisfy δi = f(Si) − f(Si−1) and submodularity gives δi ≥ δi+1.
  • Partition construction: Any independent comparison set C is partitioned into C1 through Ck so that cumulative part sizes are bounded by i · p.The partition is defined from nested availability sets Ai, with Ci = Ai−1 \ Ai.
  • Conclusion: The resulting lemma lower-bounds the value of the greedy solution for every independent comparison set in a p-independence system.The proof combines the size bound, marginal-gain bound, subadditivity, and f(Sk) = Σiδi.
  • Partition construction: Each partition part satisfies piδi ≥ fSk(Ci), linking the comparison elements’ final marginal contribution to greedy’s gain at step i.Greedy’s choice dominates every feasible element considered at that step, and submodularity transfers the bound to Sk.
  • Caveat: Stopping greedy when the best gain becomes negative can only improve its output, but the proof does not rely on this stopping rule.The stated proof remains valid without using the negative-gain termination condition.

B Proofs for Knapsack Constraints

For knapsack-constrained non-negative submodular maximization, the paper proves the existence of a polynomial-time-generated collection containing a sufficiently valuable set for every feasible comparison set.

  • Problem formulation: The knapsack problem maximizes a non-negative submodular function over sets whose total integer cost is at most B.Feasible sets satisfy c(S) ≤ B, where c(S) is the sum of selected item costs.
  • Guarantee: Theorem B.1 guarantees a polynomial-time algorithm whose collection contains, for every feasible C, a set S satisfying the theorem’s value bound.The supplied passage states the existence and polynomial-time construction but truncates the displayed approximation expression.

B.1 The Algorithm

The knapsack algorithm constructs a polynomial-size family by enumerating small initial solutions and greedily extending each one under marginal-value and budget tests.

  • Family construction: The algorithm outputs all sets of cardinality at most three and all intermediate sets from each greedy extension.This family contains O(n^4) sets because each extension has at most n elements.
  • Initialization: Every initial solution of cardinality at most three is included directly in the output family.If the comparison set has at most three elements, the algorithm outputs it itself.
  • Greedy extension: For each three-element initial set, the algorithm repeatedly selects a maximum-marginal candidate, stopping on nonpositive marginal value or updating the remaining items after budget rejection.A candidate is added only when the resulting set remains within budget B.

B.2 The Analysis

The analysis applies submodularity and greedy-order arguments to establish bounds for the constructed solution. It handles stopping and dropping cases separately before concluding that the selected set satisfies the theorem.

  • Setup: The analysis orders elements of C by the greedy algorithm’s maximum marginal value and initializes the iteration with Y = {j1, j2, j3}.The residual function is fY(S) = f(Y ∪ S) − f(Y), which remains submodular and satisfies fY(∅) = 0.
  • Setup: For elements jk outside Y, three successive submodularity inequalities bound their residual marginal values using j1, j2, and j3.Summing these inequalities provides the comparison needed later in the analysis.
  • Case analysis: When greedy stops because θτ+1 ≤ 0, every remaining term is negative, so adding C cannot improve the current solution.The analysis therefore loses no (1 − 1/e) factor in this case.
  • Case analysis: When greedy drops iτ+1 ∈ C, its cost would exceed the budget, and marginal-value-per-cost comparisons yield a contradiction if the relevant positive contribution were too large.The argument compares the dropped element with the elements selected earlier by greedy.
  • Conclusion: The final calculation gives at least (1/2)f(Sτ ∪ C), and Sτ is therefore included among the theorem’s output sets.This completes the claimed guarantee for the analyzed greedy run.

C Proofs from the Submodular Secretaries Section

This section supplies the proofs omitted from the paper’s Submodular Secretaries section. It serves as a proof-completion section rather than introducing a separate result.

  • Purpose: The section provides the missing proofs from Section 4.Its purpose is to complete the arguments for the secretary results stated earlier.
  • Scope: The omitted material belongs to the paper’s Submodular Secretaries section.The supplied passage identifies the source section as Section 4.
  • Scope: No new theorem or approximation factor is stated in the supplied passage.The passage only describes the section’s proof-completion role.

C.1 Proof for Cardinality Constrained Submodular Secretaries

The cardinality-constrained secretary proof obtains a constant approximation by separating the case of a large optimal marginal from the case where all optimal marginals are small. Randomly splitting the stream supports the latter case.

  • Result: The cardinality-constrained secretary algorithm gives an O(1) approximation to OPT.This is stated as Theorem 4.5.
  • Combination: With reasonable probability, both stream halves retain a reasonable fraction of OPT, allowing the offline algorithm on the first half to extract value from the second.The final constant is obtained by combining cases and optimizing d ← 3.08 and c ← 260.24.
  • Large marginal case: If the first optimal marginal satisfies a1 ≥ 1/c, Dynkin’s secretary algorithm selects it with probability 1/(2e), achieving a 1/(2ce) approximation.Here c ≥ 1 is a constant chosen by the analysis.
  • Small marginal case: When every optimal marginal satisfies ai < 1/c, the input is randomly partitioned into two halves and the restricted optimal solutions are compared.The first and second halves correspond to X1 and X2, with optimal restrictions C∗1 and C∗2.
  • Small marginal case: Submodularity ensures f(C∗1) + f(C∗2) ≥ f(C∗) = 1, so the proof lower-bounds the smaller half by controlling a signed random sum.The sum A uses independent uniformly random Yi ∈ {−1, 1} weighted by the optimal marginal values ai.

C.2 Proof for Partition Matroid Submodular Secretaries

The partition-matroid secretary proof models the random stream through epochs and tracks events governing whether each group’s highest element is selected. A per-group selection probability bound drives the analysis.

  • Epoch model: The random permutation can be represented by independently assigning each element a real number and placing it into an initial sample or epoch according to that number.This representation gives the same distribution over S0, …, Sk as the random input permutation.
  • Event definitions: The analysis tracks events for a group’s highest and second-highest elements, prior selection, and whether the highest element falls in or before the current epoch.A fixed tie-breaking rule makes the highest and second-highest elements unique.
  • Selection guarantee: For each group and epoch, the algorithm selects the group’s highest element according to the epoch valuation with probability at least Ω(1/k).This is the statement of Lemma 4.7.
  • Selection guarantee: Conditioning on the event that the second-highest element appeared earlier and the highest element remains eligible supports the lower bound for selecting the group maximum.The proof bounds interference from other groups using variables Qi,j and a union bound over at most k groups.

D Lower Bounds for the Constrained Submodular Maximization Problem in the Secretary Setting

The paper establishes information-theoretic lower bounds for secretary-style submodular maximization under cardinality constraints, including bounds that remain nontrivial for arbitrarily large ranks. The proofs use small COVER instances and combine them into independent puzzle instances.

  • Scope of the lower bounds: These results show that nontrivial secretary lower bounds persist for submodular functions even in the information-theoretic semi-online setting, unlike the k=1 case.For k=1, knowing OPT makes a nontrivial bound impossible; the construction therefore targets larger ranks.
  • Small-instance lower bound: The k=2 construction uses three arriving sets and an offline optimum of value 3, while online choices depend on the hidden random index r.The instance contains 1B, 2B, and rTB, with the optimum selecting rTB and the base set for the other index.
  • Small-instance lower bound: 8/9 of OPT is an upper bound for some cardinality-constrained secretary instances with k=2.The lower bound is established through a case analysis of COVER({1, 2}, {r}) when r is uniformly random.
  • Large-rank lower bound: The large-k construction decomposes COVER({1, ..., k}, S) into k/2 independent two-element puzzles generated from a random matching.Each matching edge yields an instance of COVER({i, j}, {e_r}), allowing the small lower-bound construction to be embedded repeatedly.
  • Large-rank lower bound: The proof classifies puzzles by how many elements the algorithm selects and combines their expected payoffs with the global cardinality budget.The analysis uses classes P_i, expected class sizes x_i, expected payoffs E_i, and the constraints x0+x1+x2+x3=k/2 and x1+2x2+3x3≤k.
Loading 1003.1517v2…