PaperlayerView exact revision on arXiv

Source-linked AI summary

Submodular Maximization by Simulated Annealing

Shayan Oveis Gharan, Jan Vondrák

arXiv:1007.1632v1cs.DS

TL;DR

The paper studies value-oracle maximization of nonnegative, possibly non-monotone submodular functions with and without constraints. It combines multilinear relaxation with simulated annealing, obtaining improved approximation guarantees while establishing stronger hardness thresholds for constrained variants. The paper also identifies limits on its unconstrained algorithm and a fundamental query barrier for unrestricted instances.

  • Problem

    The problem is to maximize a nonnegative submodular function, possibly under constraints, where prior approximation guarantees and value-oracle hardness left key constrained thresholds unresolved.

  • Method

    The paper combines multilinear relaxation with simulated annealing, using local search under noise that gradually decreases while maintaining solutions across stages.

  • Results

    The method achieves 0.41 for unconstrained maximization and 0.325 under matroid independence, while hardness thresholds are 0.478 for matroid independence and 0.394 for matroid bases with two disjoint bases.

  • Takeaways & Limitations

    The paper improves approximation guarantees for unconstrained and matroid-independence maximization and narrows the attainable range for several constrained problems in the value-oracle model.

  • Takeaways & Limitations

    The unconstrained algorithm cannot achieve any factor better than 17/35 ≃0.486, and unrestricted instances require exponentially many queries merely to verify whether the maximum is positive.

Abstract

from arXiv · show

We consider the problem of maximizing a nonnegative (possibly non-monotone) submodular set function with or without constraints. Feige et al. [FOCS'07] showed a 2/5-approximation for the unconstrained problem and also proved that no approximation better than 1/2 is possible in the value oracle model. Constant-factor approximation was also given for submodular maximization subject to a matroid independence constraint (a factor of 0.309 Vondrak [FOCS'09]) and for submodular maximization subject to a matroid base constraint, provided that the fractional base packing number is at least 2 (a 1/4-approximation, Vondrak [FOCS'09]). In this paper, we propose a new algorithm for submodular maximization which is based on the idea of {\em simulated annealing}. We prove that this algorithm achieves improved approximation for two problems: a 0.41-approximation for unconstrained submodular maximization, and a 0.325-approximation for submodular maximization subject to a matroid independence constraint. On the hardness side, we show that in the value oracle model it is impossible to achieve a 0.478-approximation for submodular maximization subject to a matroid independence constraint, or a 0.394-approximation subject to a matroid base constraint in matroids with two disjoint bases. Even for the special case of cardinality constraint, we prove it is impossible to achieve a 0.491-approximation. (Previously it was conceivable that a 1/2-approximation exists for these problems.) It is still an open question whether a 1/2-approximation is possible for unconstrained submodular maximization.

1 Introduction

The paper studies maximizing nonnegative submodular functions, including non-monotone cases, under unconstrained, matroid, and related constraints. It introduces simulated annealing and reports improved approximation guarantees alongside value-oracle hardness results.

  • Problem setting: Submodular maximization seeks a set maximizing a nonnegative function, possibly subject to feasibility constraints, using value-oracle access.Submodularity requires f(S ∪ T) + f(S ∩ T) ≤ f(S) + f(T).
  • Approach: Simulated annealing performs local search under decreasing random noise, initially avoiding bad local optima and becoming more refined over time.The approach is proposed as a new algorithmic framework for submodular maximization.
  • Approximation results: 0.41-approximation is achieved for unconstrained nonnegative submodular maximization, improving the previously known 0.4-approximation.The paper also notes that the algorithm cannot achieve a factor better than 17/35 ≃ 0.486 on a constructed example.
  • Approximation results: 0.325-approximation is achieved under a matroid independence constraint, improving the previously known factor of 0.309.The relevant prior work also established that better than 1/2 was impossible in the value-oracle model.
  • Hardness results: 0.478, 0.394, and 0.491 are respective value-oracle hardness thresholds for matroid independence, matroid bases with two disjoint bases, and cardinality constraints.For matroid base constraints with fractional base packing number ν = k/(k − 1), the paper gives a further threshold of 1 − e^-1/k + ϵ.

2 Preliminaries

The algorithm combines multilinear relaxation with simulated annealing. It gradually decreases a noise parameter while maintaining and locally improving the solution produced by earlier stages.

  • Multilinear relaxation: Multilinear relaxation replaces discrete optimization over feasible sets with continuous optimization of the multilinear extension over the associated polytope.For unconstrained sets, matroid independent sets, and matroid bases, fractional solutions can be rounded without decreasing the function value.
  • Simulated annealing: Simulated annealing is modeled by independently adding or removing each element with probability t and optimizing the resulting expected function value.The expectation equals the multilinear extension evaluated at a vector determined by the current set and t.
  • Simulated annealing: The process starts at t = 1/2, decreases t gradually, and ends at t = 0, where local search becomes ordinary approximate local search.At t = 1/2 the objective is independent of the current set, while t = 0 removes fluctuations.
  • Analysis: The algorithm maintains the solution from previous stages rather than restarting local search separately for each temperature.Its performance is analyzed through a differential equation whose initial condition relates to a previously known algorithm.

3 Unconstrained Submodular Maximization

The unconstrained algorithm combines local search with a gradually changing simulated-annealing parameter, proving a 0.41-approximation with high probability. Its analysis shows that insufficiently valuable local optima improve as the parameter increases, while practical implementation requires approximate local optimization.

  • Algorithm and guarantee: Simulated annealing increases p from 1/2 toward 1, using δ = 1/n^3 and retaining the best encountered solution.The algorithm is presented as a loop over discretized parameter values and returns the best solution among encountered sets and complements.
  • Implementation caveat: The analysis assumes a true local optimum, although standard approximate stopping and random-sampling techniques can address implementation issues.As stated, finding a local optimum in the specified steps would prevent polynomial running time.
  • Algorithm and guarantee: 0.41-approximation: Algorithm 1 returns with high probability a set whose value is at least 0.41 · OPT.The algorithm's input is a nonnegative submodular function and its output is a subset of the ground set.
  • Analysis: Unless the current solution is already sufficiently valuable, increasing p yields a positive improvement, which produces a differential-equation analysis of the algorithm's evolution.The proof combines derivative bounds with nonnegative progress from local search.
  • Algorithm and guarantee: At each parameter value, local search seeks to maximize F(x_p(A)), where x_p(A) assigns coordinate p to elements in A and 1 − p otherwise.The local optimum condition compares the value after flipping each element's membership in A.
  • Analysis: The starting point is chosen carefully: p_0 = 1/2 with the random value v_0 = 1/4 gives no improvement, whereas another starting point yields β > 0.41.The resulting differential equation reaches a parameter p_1 with Φ(p_1) ≥ β.

4 Matroid Independence Constraint

For matroid independence constraints, the paper gradually relaxes a box-constrained matroid polytope and uses fractional local search, exchange matchings, and pipage rounding. This yields a 0.325-approximation with high probability.

  • Algorithm and guarantee: The method optimizes the multilinear extension over P_t(M) = P(M) ∩ [0,t]^X while increasing t from 0 to 1.The fractional solution is ultimately rounded using pipage rounding.
  • Algorithm and guarantee: Temperature relaxation cannot simply increase every saturated coordinate, because doing so may violate the matroid constraint.The algorithm instead selects variables that can be increased through a bipartite fractional exchange graph and matching.
  • Algorithm and guarantee: Fractional local search uses feasible directions in {±e_i, e_i − e_j}, while complementary candidate solutions are also checked before returning the best encountered solution.The implementation records local independent-set candidates and updates the fractional representation through exchanges.
  • Algorithm and guarantee: 0.325-approximation: Algorithm 2 returns with high probability an independent set worth at least 0.325 · OPT.Here OPT is the maximum value over independent sets of the matroid.
  • Analysis: The proof relates temperature-relaxation gains to a matching weight and uses local optimality, submodularity, and König's theorem to establish the needed improvement.This leads to a differential equation analogous to the unconstrained analysis.
  • Analysis: Starting from the 0.309 approximation at t_0 = 1/2, the analysis finds β > 0.325 at a temperature roughly 0.53.The precise differential-equation analysis is deferred to the appendix.

5 Hardness of approximation

The paper strengthens value-oracle hardness results for constrained nonnegative submodular maximization using symmetry gaps and directed hypergraph cut constructions.

  • Symmetry-gap framework: Symmetry-gap analysis compares the unrestricted multilinear optimum with the best symmetric fractional solution, yielding exponential-query hardness for refined instances.The refinement preserves the constraint type while blowing up the original instance.
  • Hard-instance construction: Directed hypergraph cut functions provide nonnegative submodular hard instances, with a hyperedge cut when a tail is selected and its head is not.The construction uses directed hyperedges with one head and a nonempty tail set.
  • Matroid base constraints: 0.394-approximation is impossible under a matroid base constraint, even when the matroid contains two disjoint bases.The explicit partition-matroid example has base packing number 2.

A Miscellaneous Lemmas

These lemmas characterize how the multilinear extension changes under coordinate increases and relate it to threshold-generated random sets.

  • Multilinear extension: For simultaneous coordinate increases, the change in the multilinear extension is bounded using partial derivatives at the lower and upper endpoints.A twice-differentiability argument formalizes the corresponding first-order approximation.
  • Multilinear extension: Submodularity makes every mixed second partial derivative of the multilinear extension nonpositive.Consequently, partial derivatives cannot increase when coordinates move upward.
  • Threshold methods: The threshold lemma lower-bounds the multilinear extension by the expected value of a random threshold set.Threshold sets contain elements whose fractional coordinates exceed a uniformly random λ.
  • Threshold methods: Applying thresholds to vectors mixing the optimum and another set decomposes the bound into expectations over the optimum, an intersection, and the empty set.For x = p1_A∩C + (1−p)1_B∩C, the three threshold ranges have probabilities 1−p, 2p−1, and 1−p.

B Analysis of the 0.41-approximation

The analysis tracks the simulated-annealing solution as temperature decreases, deriving a differential inequality and optimizing its resulting lower bound to exceed 0.41.

  • Continuous analysis: The analysis models the solution value Φ(p) continuously as temperature decreases and derives a differential inequality for its evolution.The argument takes the δ → 0 limit and assumes OPT = 1 without loss of generality.
  • Optimization of the bound: A naive uniformly random 1/4 starting point does not match the prior 2/5 guarantee, motivating a stronger temperature-dependent local-optimum analysis.The initial choice p0 = 1/2 and v0 = 1/4 yields a bound strictly below 2/5.
  • Final guarantee: β > 0.41 completes the proof of the unconstrained approximation guarantee.The authors note that an intermediate 61/150 bound does not itself establish the final 0.41 result.
  • Continuous analysis: The key bound combines the multilinear value with local-optimum values f(A) and f(B), using submodularity and a target upper bound β.Under f(A), f(B) ≤ β, it obtains 2F(x) ≥ (1−q^2)OPT − 2q(1−2q)β.
  • Optimization of the bound: Starting from an initial value v0 at p0, integrating the inequality produces a quadratic lower bound for Φ(p).The bound is optimized over p to select the best point along the annealing process.

C Upper Bounding the Performance of the Simulated Annealing Algorithm

The section constructs a directed-cut instance where simulated annealing can follow local optima yielding only 17/35 < 0.486 of the optimum, so the algorithm fails to guarantee a half-approximation.

  • 0.486 is an upper bound on the approximation ratio of Algorithm 1 for a constructed unconstrained instance.Theorem C.1 states the ratio is 17/35 < 0.486.
  • The hard instance uses a directed graph whose cut function is submodular, with local optima A and B across different temperature ranges.A is locally optimal for p ∈ [1/4, 3/4], while B is locally optimal for p ∈ [3/4, 1].
  • 17/35 results when the algorithm follows A from p = 1/2 to 3/4 and then switches to B until the end.Both local optima have the same multilinear-extension value at p = 3/4, allowing this path.
  • The optimum set {4, 5, 6, 7} has value 35, whereas the algorithm’s relevant sets or their probabilistic combination have value at most 17.

D Analysis of the 0.325-approximation

The analysis proves a 0.325 approximation for matroid-constrained maximization by relating temperature-relaxation gains to derivatives toward the optimum and solving the resulting differential equation.

  • The analysis compares the temperature-relaxation gain with G(x) = (1_C − x) · ∇F(x), the derivative toward an optimal solution.This comparison is the key step in the proof of Lemma 4.5.
  • A maximum-weight matching encodes feasible coordinate changes when temperature relaxation cannot increase every positive-derivative coordinate directly.Matroid exchange mappings ensure that the resulting modifications preserve independence.
  • König’s theorem supplies a matching through edge coloring of the relevant bipartite graph, enabling a lower bound on positive edge weight.The graph’s maximum degree is bounded by (1 − t)N under the assumption n ≤ (1 − t)N.
  • The multilinear-extension value cannot decrease during fractional local search after temperature relaxation.The next fractional point is obtained by applying fractional local search to the relaxed point.
  • 0.325 is achieved because, for some t roughly 0.53, the analyzed function satisfies Φ(t) ≥ β with β > 0.325.The proof obtains β by solving the differential-equation bound under the initial 0.309-approximation conditions.

E.1 Matroid base constraints

For matroid base constraints, the paper strengthens prior hardness results: achieving 1 − e^-1/ℓ + ε may require exponentially many value queries when the fractional base packing number is ℓ/(ℓ−1).

  • 1 − e^-1/ℓ + ε requires exponentially many value queries for some base-constrained instances with fractional base packing number ν = ℓ/(ℓ−1).This generalizes the ℓ = 2 threshold discussed in the section.
  • The hard instances use feasible bases containing ℓ−1 vertices from A and one vertex from B.The optimum can select heads of the first ℓ−1 hyperedges and one tail of the last hyperedge, retaining OPT = 1.
  • Refinement yields matroids whose feasible bases contain an (ℓ−1)/ℓ fraction of A and a 1/kℓ fraction of B.The refined instances have fractional base packing number ℓ/(ℓ−1).
  • Figure 4 contrasts the independence-constraint construction with two weighted directed hyperedges and a weighted edge between a and b.The constraint permits at most one selected vertex from each of A and B.

E.2 Matroid independence constraint

For matroid independence constraints, a perturbed directed-hypergraph construction yields a 0.478 value-oracle hardness threshold using a partition matroid.

  • The construction uses directed hypergraph cut functions, which are submodular when each directed hyperedge has exactly one head.
  • 0.478-approximation requires exponentially many value queries for some nonnegative submodular maximization instances over matroid-independent sets.This is Theorem E.2’s hardness statement.
  • The initial construction fails to exceed a 1/2 hardness threshold because its multilinear relaxation has value 1/2 at a feasible symmetrized vector.That vector favors selecting vertices from B rather than the heads set A.
  • Adding an undirected edge of weight 1 − α and reducing the hyperedge weights to α preserves OPT = 1 while forcing nonzero head-coordinate values in the symmetrized solution.The added edge contributes when exactly one of a and b is selected.
  • Numerical optimization gives α ≃ 0.3513 and OPT ≃ 0.4773 for the perturbed construction.The refined instances are independent sets of a partition matroid.

E.3 Cardinality constraint

The section establishes a 0.491 hardness threshold for nonnegative submodular maximization under a cardinality constraint, including exponentially many value-query requirements. The exact-cardinality variant is at least as difficult as the at-most-cardinality problem.

  • Hardness result: 0.491-approximation requires exponentially many value queries for some instances with |S| ≤ ℓ.This is stated for max{f(S) : |S| ≤ ℓ} with f nonnegative submodular.
  • Reduction: The exact-cardinality problem max{f(S) : |S| = k} is at least as difficult to approximate as the at-most-cardinality problem.The reduction tries all values k = 0, 1, 2, ..., ℓ.
  • Proof strategy: The proof evaluates the multilinear-extension optimum using a hypergraph cut function and the feasibility polytope for the cardinality-constrained instance.The construction sets ℓ = 2 and uses equations from the preceding theorem to compute the relevant values.
  • Hardness construction: The hardness construction uses a cardinality constraint requiring selection of at most a 1/(k+1) fraction of the ground-set elements.The refined instances achieve γ ≃ 0.49098 when α ≃ 0.15.
Loading 1007.1632v1…