PaperlayerView exact revision on arXiv

Source-linked AI summary

Non-monotone submodular maximization under matroid and knapsack constraints

Jon Lee, Vahab Mirrokni, Viswanath Nagarjan, Maxim Sviridenko

arXiv:0902.0353v1cs.CCcs.DS

TL;DR

The paper addresses non-monotone submodular maximization under multiple matroid or knapsack constraints, extending approximation algorithms to settings with side constraints. It develops constant-factor algorithms, including improved guarantees for partition matroids.

  • Problem

    Non-monotone submodular maximization covers important combinatorial problems but remains NP-hard and requires approximation algorithms that handle multiple side constraints.

  • Method

    The paper develops approximation algorithms using fractional relaxation for knapsack constraints and local search, including larger exchange moves for partition matroids.

  • Results

    The paper gives the first constant-factor approximation algorithms for non-monotone submodular maximization under multiple matroid or knapsack constraints and improves guarantees for partition matroids.

  • Takeaways & Limitations

    The results extend constant-factor approximation to constrained non-monotone submodular maximization and strengthen the treatment of partition matroid constraints.

  • Takeaways & Limitations

    The exact local-search algorithm may require exponential time before reaching a locally optimal solution, motivating approximate local search.

Abstract

from arXiv · show

Submodular function maximization is a central problem in combinatorial optimization, generalizing many important problems including Max Cut in directed/undirected graphs and in hypergraphs, certain constraint satisfaction problems, maximum entropy sampling, and maximum facility location problems. Unlike submodular minimization, submodular maximization is NP-hard. For the problem of maximizing a non-monotone submodular function, Feige, Mirrokni, and Vondrák recently developed a $2\over 5$-approximation algorithm \cite{FMV07}, however, their algorithms do not handle side constraints.} In this paper, we give the first constant-factor approximation algorithm for maximizing any non-negative submodular function subject to multiple matroid or knapsack constraints. We emphasize that our results are for {\em non-monotone} submodular functions. In particular, for any constant $k$, we present a $({1\over k+2+{1\over k}+ε})$-approximation for the submodular maximization problem under $k$ matroid constraints, and a $({1\over 5}-ε)$-approximation algorithm for this problem subject to $k$ knapsack constraints ($ε>0$ is any constant). We improve the approximation guarantee of our algorithm to ${1\over k+1+{1\over k-1}+ε}$ for $k\ge 2$ partition matroid constraints. This idea also gives a $({1\over k+ε})$-approximation for maximizing a {\em monotone} submodular function subject to $k\ge 2$ partition matroids, which improves over the previously best known guarantee of $\frac{1}{k+1}$.

1 Introduction

The paper addresses non-monotone submodular maximization under matroid and knapsack constraints, extending approximation algorithms beyond the unconstrained setting. It develops constant-factor guarantees for multiple constraints and improves bounds for partition matroids.

  • Non-monotone submodular maximization is NP-hard and models problems including graph cuts, facility location, entropy sampling, and constraint satisfaction.
  • Earlier non-monotone algorithms did not handle extra constraints, while monotone results did not generalize to non-monotone functions.
  • The paper gives the first constant-factor approximation algorithms for non-negative non-monotone submodular maximization under multiple matroid or knapsack constraints.
  • For knapsack constraints, the approach combines an approximation algorithm for a fractional relaxation with randomized rounding to obtain an integral solution.

2 Matroid Constraints

The paper develops local-search algorithms for maximizing non-negative non-monotone submodular functions under k matroid constraints. Exchange and deletion operations support the analysis, yielding approximation guarantees with n^O(k) running time and stronger bounds in special cases.

  • Problem: The problem maximizes a non-negative submodular function over sets independent in each of k matroids on a common ground set.The algorithm uses value-oracle access to the function.
  • Local search: Local search repeatedly applies feasible exchange operations that add one element while dropping up to k elements, or deletes elements when deletion improves the objective.For k = 1 and equal-size solutions, the exchanges reduce to swap operations.
  • Analysis: Matroid exchange mappings associate each candidate element with at most one removable element per matroid, enabling inequalities that compare a locally optimal solution with any feasible comparator.These inequalities combine submodularity with local optimality under exchanges and deletions.
  • Analysis: (k + 1) · f(S) ≥ f(S ∪ C) + k · f(S ∩ C) holds for a locally optimal solution S and any common independent set C.For k = 1 with equal-size sets and swap-only local optimality, the stronger bound is 2 · f(S) ≥ f(S ∪ C) + f(S ∩ C).
  • Guarantees: Algorithm A achieves an approximation guarantee for any k matroid constraints in time n^O(k), while approximate local search is used to avoid potentially exponential exact local-search duration.For constant k, the stated running time is polynomial in n.
  • Symmetric functions: For symmetric submodular functions, one approximate local-search iteration suffices instead of k + 1 iterations.The symmetry-based analysis derives the guarantee from the union and intersection terms.

3 Knapsack constraints

For k knapsack constraints, the paper combines a fractional relaxation with approximate local search and randomized rounding. The resulting approach terminates in polynomial time and gives a (1/5 − ε)-approximation.

  • Problem: The knapsack problem maximizes a non-negative submodular function subject to k weight constraints with capacities C1, …, Ck.The function is evaluated through its multilinear fractional extension.
  • Fractional relaxation: The fractional relaxation maximizes F(y) subject to all knapsack inequalities and coordinate upper bounds 0 ≤ yi ≤ ui.After scaling, each knapsack capacity is normalized to 1.
  • Fractional optimization: Approximate local search changes at most k variables up and k variables down on a discrete grid, accepting moves that improve F by a factor 1 + ε.The neighborhood has size n^O(k).
  • Running time: O(ε^-1 log n) local-search iterations suffice, so the fractional procedure terminates in polynomial time.The initialization uses a singleton with maximum ui · f({i}).
  • Analysis: The fractional analysis establishes (2 + 2n · ε) · F(y) ≥ F(y ∧ x) + F(y ∨ x) − 1 for a local optimum y and feasible x.The proof uses decomposition into small-support vectors and the submodularity of an induced set function g.
  • Guarantee: (1/5 − ε)-approximation is obtained for submodular maximization subject to k knapsack constraints.The paper states the result for any constant δ > 0 in the preceding fractional theorem and leaves details in Appendix C.

4 Improved Bounds under Partition Matroids

The partition-matroid improvement strengthens the local-search exchange step by adding multiple elements at once, yielding improved guarantees for partition matroids.

  • Local-search improvement: Allowing p new elements in an exchange while dropping up to (k −1)·p elements strengthens the local-search move.The general procedure adds one element and drops up to k elements; the partition-matroid variant uses fixed constant p ≥1.
  • Local-search improvement: The strengthened analysis is based on an extension of Lemma 2 for local-optimal solutions.For local optimum S and feasible comparison set C, the analysis relates f(S), f(S ∪ C), and f(S ∩ C).
  • Analysis: The exchange construction combines the partition matroids through mappings that form a maximum-degree-two multigraph.Each edge corresponds to an exchange label, and the graph decomposes into disjoint components.
  • Analysis: k · f(S) ≥ f(S ∪ Rq) + (k −1) · f(S ∩ C) for every q ∈ {0, · · · , p −1}.The inequality is obtained for the family of exchange sets Rq used in the strengthened local-search analysis.

A Missing proofs from Section 2

These proofs establish inequalities for exact and approximate local optima and explain why the local-search procedures remain polynomial-time.

  • Exchange proof: The exchange-map proof uses matroid exchange properties to construct feasible replacements between independent sets and bases.The construction proceeds inductively and can be reduced to an exchange between two bases in a truncated matroid.
  • Local-optimality bounds: 2(1 + ε) · f(S) ≥ f(S ∪ C) + f(S ∩ C) for equal-sized independent sets under a single matroid.This is the k = 1 specialization for a locally optimal solution under swap operations.
  • Local-optimality bounds: (1 + ε)(k + 1) · f(S) ≥ f(S ∪ C) + k · f(S ∩ C) for an approximately locally optimal solution under k matroids.The approximate-local-optimality factor enters by multiplying the corresponding local-search inequalities by 1 + ε.
  • Runtime: Approximate local operations increase the objective by a factor 1 + ε, making the number of local operations polynomial in n.The initial singleton value is at least Opt(X)/n, and the paper bounds the resulting procedure runtime polynomially for fixed k.

B Missing Proofs from Section 3

The missing proofs analyze continuous extensions of submodular functions and fractional local search, then establish the desired fractional approximation through a scaled-copy argument.

  • Continuous extension: The multilinear extension is shown to preserve the relevant submodularity property through nonpositive mixed partial derivatives.The proof uses continuous submodularity and derivative monotonicity to compare function differences at coordinate-wise ordered points.
  • Fractional local search: The algorithm performs two fractional local searches with complementary upper bounds and returns the better of y1, y2, and the best singleton value.The second search uses upper bounds ui = 1 − y1(i).
  • Fractional guarantee: (2 + δ) · F(y1) ≥ F(x ∧ y1) + F(x ∨ y1) − fmax and an analogous inequality holds for y2.Combining the two local-optimality inequalities with the scaled-copy submodularity argument yields the fractional guarantee.
  • Scaled-copy argument: A scaled ground set with multiple copies of each element converts fractional vectors into integral sets while preserving submodularity.Sets A, B, and C represent y1, y2, and x; their intersections and unions correspond to the fractional operations in the analysis.
  • Fractional guarantee: The proof concludes that the fractional local-search method achieves the desired approximation for the fractional problem.The supplied passage states the resulting approximation without reproducing its full numerical expression.

C Rounding the fractional solution under knapsack constraints

For knapsack constraints, the rounding analysis separates heavy and light elements, solves a fractional light-element relaxation, and controls feasibility through independent sampling and concentration bounds.

  • Heavy and light elements: Heavy elements are enumerated, while light elements are handled by fractional optimization followed by randomized rounding.An element is heavy when wi(e) ≥ δ for some knapsack; otherwise it is light, and at most k/δ heavy elements occur in an optimum.
  • Randomized rounding: The fractional relaxation for light elements is solved first, then each element e is sampled independently with probability (1 − ε)·xe.The algorithm outputs the empty set if the sampled set violates any knapsack, ensuring feasibility.
  • Feasibility control: Pr[α(S) ≥ a] ≤ k · e^(−c a k^2) for any a ≥ 1, where α(S) is the maximum normalized knapsack load.Chernoff bounds provide the tail estimate because the rounded light-element contributions are independent and bounded.
  • Light-element analysis: The light-element rounding algorithm obtains an expected value bounded below by the paper’s stated constant-factor expression.The analysis combines the tail bound with an upper bound on values of overloaded sets.
  • Main guarantee: A (1/5 − η)-approximation algorithm exists for maximizing a non-negative submodular function over k knapsack constraints.The guarantee holds for any constant η > 0.
  • Main guarantee: The better solution from heavy-element enumeration and light-element rounding yields the 1/5 − η guarantee.Subadditivity relates the optimal value f(H ∪ L) to f(H) + f(L), enabling the two candidates to be combined.

D Missing Proofs from Section 4

This section develops local-search arguments for submodular maximization under multiple partition matroids, covering both non-monotone and monotone cases. It also gives a tight example showing that the greedy guarantee for monotone functions cannot generally improve.

  • Missing Proofs from Section 4: p-exchange local search yields a polynomial-time approximation framework for monotone submodular maximization under multiple partition matroids.The method uses p-exchanges, with p chosen to control the approximation quality and running time.
  • Missing Proofs from Section 4: The monotone analysis obtains a k + ε approximate solution through the chosen local-search parameterization.The supplied proof fragment states that S is a k + ε approximate solution after setting p appropriately.
  • Missing Proofs from Section 4: For non-monotone functions, repeating p-exchange local search k times gives inequalities relating each local solution S_i to the residual optimum C_i.The analysis establishes k · f(S_i) ≥ f(S_i ∪ C_i) + (k − 1) · f(S_i ∩ C_i).
  • Missing Proofs from Section 4: The monotone result improves the previously best-known 1/(k+1) guarantee, including for the special case of partition matroids.The passage explicitly identifies this as the first improvement over the greedy 1/(k+1)-approximation algorithm.
  • Missing Proofs from Section 4: The greedy bound is tight: a constructed coverage instance has optimum value |E| = p(k + 1) + 1, while greedy obtains only p + 1.The construction uses k partition matroids, each forbidding the simultaneous selection of S0 and Sj.

E Matroid Base Constraints

The paper studies non-negative submodular maximization over matroid bases. It obtains stronger guarantees for symmetric functions and for matroids containing two disjoint bases, while showing that swap-only local search can fail badly without symmetry.

  • Symmetric submodular functions: A 1/3 − ε-approximation is available for maximizing a non-negative symmetric submodular function over bases of any matroid.The algorithm uses approximate local search with swap operations to obtain polynomial running time.
  • Symmetric submodular functions: Without symmetry, the swap-based algorithm can have an arbitrarily bad approximation guarantee.In the directed-cut example, U is optimal while V is a swap-local optimum.
  • Matroid base constraints: For matroids containing two disjoint bases, a 1/6 − ε-approximation is obtained for any non-negative submodular function over bases.The algorithm first finds S1 by swaps, then searches outside S1 using exchanges and deletions before contracting S2.
  • Matroid base constraints: The proof combines local-search inequalities with two disjoint bases in the contracted matroid to lower-bound the solution value by the optimum.The disjoint bases B1 and B2 support the second inequality in the displayed chain.
  • Matroid base constraints: For cardinality-constrained maximization, the same 1/6 − ε guarantee applies to every target size c.The argument reduces larger cardinalities to their complements using g(T) = f(V \ T).
Loading 0902.0353v1…