Source-linked AI summary
Symmetry and approximability of submodular maximization problems
Jan Vondrak
TL;DR
The paper addresses how to derive value-oracle inapproximability results for submodular maximization from multilinear-relaxation symmetry gaps. It provides a general refinement-based construction, proving exponential-query barriers including no constant-factor approximation over matroid bases, alongside closely matching approximation guarantees.
Problem
Existing submodular maximization hardness results use the value-oracle model, but the relationship between multilinear-relaxation thresholds and oracle inapproximability is not fully understood.
Method
The paper defines a symmetry gap for strongly symmetric instances and transfers it automatically to refined instances and their multilinear relaxations.
Results
Any constant-factor approximation for nonnegative submodular maximization over matroid bases requires exponentially many value queries.
Takeaways & Limitations
The framework unifies several known value-oracle hardness results, yields new ones, and supports closely matching approximation algorithms for matroid-constrained problems.
Takeaways & Limitations
The corrected general theorem requires stronger symmetry conditions because membership-oracle queries can reveal information about hidden optimal solutions.
Abstract
from arXiv · showhide
A number of recent results on optimization problems involving submodular functions have made use of the multilinear relaxation of the problem. These results hold typically in the value oracle model, where the objective function is accessible via a black box returning f(S) for a given S. We present a general approach to deriving inapproximability results in the value oracle model, based on the notion of symmetry gap. Our main result is that for any fixed instance that exhibits a certain symmetry gap in its multilinear relaxation, there is a naturally related class of instances for which a better approximation factor than the symmetry gap would require exponentially many oracle queries. This unifies several known hardness results for submodular maximization, and implies several new ones. In particular, we prove that there is no constant-factor approximation for the problem of maximizing a non-negative submodular function over the bases of a matroid. We also provide a closely matching approximation algorithm for this problem.
1 Introduction
The paper develops symmetry-gap hardness constructions for submodular maximization in the value-oracle model and applies them to matroid constraints. It also gives closely matching approximation algorithms for matroid-base and matroid-independence variants.
- Background and motivation: The multilinear relaxation enables continuous optimization and rounding fractional solutions to discrete ones for matroid constraints.Its exact value can be estimated by random sampling rather than computed by querying all 2^n sets.
- Symmetry-gap hardness: The paper’s general construction converts a symmetry gap in a strongly symmetric instance into exponential value-query hardness for refined instances.For every ε > 0, achieving a (1+ε)γ-approximation is hard when γ is the symmetry gap.
- Matroid-base maximization: Any constant-factor approximation for nonnegative submodular maximization over matroid bases requires exponentially many value queries.The lower bound also applies to randomized algorithms and is independent of assumptions such as P ≠ NP.
- Extensions: The same symmetry-gap framework yields exponential-query hardness for multilinear optimization and matroid-independent-set maximization.The paper also reports an improved 0.309-approximation for nonmonotone submodular maximization under a matroid independence constraint.
2 From symmetry to inapproximability: applications
The symmetry-gap framework yields hardness results for several submodular maximization problems, including a new impossibility result for matroid bases, while also clarifying limits of the technique.
- Applications: A symmetry-gap construction recovers known hardness thresholds for monotone cardinality-constrained and nonmonotone submodular maximization.For monotone cardinality constraints, any approximation better than 1−(1−1/k)^k requires exponentially many value queries; the limit is 1−1/e. For nonmonotone cardinality constraints, the hardness threshold is 1/2.
- Applications: No constant-factor approximation exists for maximizing a nonnegative nonmonotone submodular function over the bases of a general matroid.The result follows from instances whose fractional base packing number is ν = k, for which any approximation better than 1/k requires exponentially many value queries.
- Applications: The multilinear relaxation has the same hardness factors as the corresponding discrete problems when fractional solutions can be rounded without loss.This applies in particular to the matroid-bases result, yielding no constant-factor approximation for the associated multilinear optimization problem.
- Limits: The symmetry-gap technique cannot establish constant-factor hardness for monotone submodular maximization under the intersection of k matroid constraints.Such a result would also contradict the known (1−1/e)-approximation for the corresponding multilinear problem.
- Limits: Symmetry-gap hardness reflects difficulty in solving the multilinear optimization problem rather than difficulty in rounding fractional solutions.The technique is therefore primarily suited to problems where the multilinear relaxation closely captures the original discrete problem.
3 From symmetry to inapproximability: proof
The proof transforms a fixed symmetric instance and its symmetry gap into refined, hard-to-distinguish instances whose optimum values retain essentially the same gap.
- Construction: The construction compares the multilinear extension F(x) with its symmetrized version G(x)=F(¯x), then perturbs both to agree near symmetric points.The modified functions induce discrete instances on refined ground sets by interpreting fractional variables as fractions of clusters.
- Construction: A symmetry-preserving refinement converts the modified continuous functions into discrete submodular objectives and a feasibility system based on ξ(S).Feasibility depends only on the symmetrized vector, so the hidden permutations used in the refinement do not affect membership queries.
- Hardness: Exponential oracle complexity follows because randomized algorithms cannot distinguish the two refined instances with any constant probability of success using subexponentially many queries.The proof first shows that deterministic algorithms follow the same computation path with high probability, then applies Yao’s principle.
- Hardness: The refined instances preserve a gap arbitrarily close to the original symmetry gap γ.The first instance approximates the original optimum, while the symmetrized instance is bounded by γOPT up to arbitrarily small additive error.
- Hardness: The resulting hard instances inherit strong symmetries from the group action, including permutations among copies and permutations of copy classes.This establishes hardness even for instances satisfying these additional symmetry properties.
4 Algorithms using the multilinear relaxation
For nonmonotone submodular maximization under matroid constraints, the paper uses fractional local search over a bounded matroid polytope followed by pipage rounding to obtain approximation guarantees.
- Matroid independence constraint: Fractional local search optimizes the multilinear extension over P_t(M)=P(M)∩[0,t]^X using add, remove, and switch moves.The bounded box is intended to keep fractional solutions fuzzier than integral ones, and the search maintains a structured decomposition into independent sets.
- Matroid independence constraint: Pipage rounding converts the resulting fractional solution into an integral feasible solution without loss in objective value.The rounding step is adapted to preserve the multilinear objective for the matroid setting.
- Matroid bases: For matroid bases, fractional local search and rounding provide a closely matching positive result to the symmetry-gap hardness.The algorithm can use the matroid or its dual to exploit a better fractional base packing, and obtains a 1/4−o(1)-approximation for uniform matroids.
5 Approximation for symmetric instances
The section develops approximation guarantees for symmetric submodular maximization instances, using symmetry to identify useful fractional solutions and local optima. For matroid independence and base constraints, these guarantees match corresponding value-oracle hardness thresholds up to lower-order terms.
- Symmetric instances: Symmetry in the instance can yield approximation guarantees matching the hardness threshold up to lower-order terms.The same symmetry is used in both the approximation and hardness constructions.
- Symmetric instances: A symmetric optimum is a local optimum for the original multilinear-relaxation problem.The proof uses invariance of the objective and feasible region under permutations.
- Element-transitive instances: (1/2 −o(1))-approximation is achievable for matroid independence constraints under element-transitive symmetry.All symmetric solutions have equal coordinates, so the best one can be found by binary search over a one-parameter family.
- Element-transitive instances: The (1/2 −o(1))-approximation is optimal for element-transitive instances because any (1/2 + ε)-approximation would require exponentially many value queries.The hard instances used for the lower bound are themselves element-transitive.
- Totally symmetric instances: For totally symmetric matroid-base instances, the center point achieves a 1/2(1 −1/max{ν, ν∗} −o(1))-approximation.When ν = ν∗, this improves to the optimal factor 1 −1/ν.
- Totally symmetric instances: For partition matroids satisfying the stated α-fraction bounds, the center point satisfies F(c) ≥α · OPT.The hard instances have α = 1/k, ν = 1/(1 −α), and any (α + ε)-approximation requires exponentially many value queries.
A Submodular functions and their extensions
The section defines multilinear and Lovász extensions through randomized set constructions and compares their properties. The Lovász extension is convex for submodular functions and is upper-bounded by the multilinear extension.
- Extensions: The multilinear extension F(x) equals the expected value of f on a set sampled independently with inclusion probabilities x_i.This interpretation underlies the continuous relaxation used for submodular maximization.
- Extensions: The Lovász extension samples a random set in a correlated fashion using a uniformly random threshold set.The threshold set includes elements whose coordinates exceed the random threshold.
- Comparison: The Lovász extension of a submodular function is always convex, unlike the multilinear extension.The section establishes this contrast as a basic structural property.
- Comparison: The Lovász extension is upper-bounded by the multilinear extension for submodular functions.This comparison is formalized as Lemma A.4.
- Hybrid construction: Independent sampling on a partition can be replaced partwise by independent threshold sets, producing a hybrid between the multilinear and Lovász extensions.The proof proceeds by conditioning on one part and applying the extension comparison repeatedly.
B Pipage rounding for nonmonotone submodular functions
The section extends pipage rounding to nonmonotone submodular maximization under matroid constraints. An adjustment procedure preserves or improves multilinear value before rounding, yielding independent sets with expected value at least the fractional value.
- Pipage rounding: Pipage rounding converts a point in the matroid base polytope into a random base with expected value at least F(y).The guarantee holds with membership and value oracles.
- Scope: Monotonicity is unnecessary when rounding points already lying in the base polytope, but additional adjustment is needed for general matroid-polytope points.The adjustment ensures that rounding does not lose objective value.
- Adjustment: The adjustment procedure transforms x ∈P(M) into a restricted matroid M′ and y ∈B(M′) with E[F(y)] ≥F(x).It repeatedly increases fractional coordinates to their maximum or sets them to zero and deletes them.
- Adjustment: The adjustment process preserves the expected multilinear objective because each randomized coordinate update forms a martingale.The final expected value equals the initial F(x).
- Adjustment: The adjustment procedure terminates in O(n^2) time.Each variable is increased at most once before either reaching its maximum or being removed.
- Extended rounding: Extended pipage rounding produces a random independent set S with E[f(S)] ≥F(x) for every x in the matroid polytope.It applies Adjust followed by PipageRound.
C Solutions of nontrivial value
The section establishes that nonnegative nonmonotone submodular maximization under matroid independence or base constraints always has solutions with nontrivial value. It also gives a directed-cut example showing that the base-constraint bound is tight up to a constant factor.
- Assumptions: The assumptions exclude loops and, for base constraints, coloops because these elements can be removed or contracted beforehand.These preprocessing conditions are used to ensure the stated sampling and value bounds.
- Independence constraints: For matroid independence constraints without loops, the best independent-set value is bounded below relative to the unconstrained maximum by Lemma C.1.The proof considers only independent sets of size at most one and uses submodularity and nonnegativity.
- Base constraints: For matroid bases without loops or coloops, Lemma C.2 gives a nontrivial lower bound on the best base value relative to the unconstrained maximum.The proof constructs a base greedily by repeatedly choosing an eligible element of maximum marginal value.
- Base constraints: A greedy base construction uses decreasing marginal values to relate its value to the unconstrained optimum.The argument addresses the possibility that later elements decrease the current value.
- Tightness example: In the directed-cut example, every feasible base has value 1 while the unconstrained optimum is n^2/4.The matroid bases contain exactly one element from X1 and n−1 elements from X2.