PaperlayerView exact revision on arXiv

Source-linked AI summary

Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes

Chandra Chekuri, Jan Vondrák, Rico Zenklusen

arXiv:1105.4593v5cs.DMcs.DS

TL;DR

The paper addresses limited techniques for maximizing non-negative, potentially non-monotone submodular functions under varied packing and independence constraints. It develops multilinear relaxation and contention-resolution methods, obtaining constant-factor optimization over solvable down-closed polytopes and broadly combinable rounding schemes, including an optimal scheme for matroids.

  • Problem

    Existing multilinear-relaxation methods had limited constant-factor guarantees for non-monotone objectives and lacked a general solution for arbitrary solvable polytopes and mixed constraints.

  • Method

    The framework approximately maximizes the multilinear extension over a constraint polytope and rounds the fractional solution using contention resolution schemes.

  • Results

    The paper gives a first constant-factor approximation over any down-monotone solvable polytope and schemes that combine across constraints, including an optimal matroid scheme.

  • Takeaways & Limitations

    The framework provides a broadly applicable approach for maximizing linear and submodular functions under varied independence constraints.

  • Takeaways & Limitations

    Knapsack applications incur an O(nn0) enumeration factor in running time, although knapsacks can be combined with other constraint types without significantly affecting the approximation ratio.

Abstract

from arXiv · show

We consider the problem of maximizing a non-negative submodular set function $f:2^N \rightarrow \mathbb{R}_+$ over a ground set $N$ subject to a variety of packing type constraints including (multiple) matroid constraints, knapsack constraints, and their intersections. In this paper we develop a general framework that allows us to derive a number of new results, in particular when $f$ may be a non-monotone function. Our algorithms are based on (approximately) maximizing the multilinear extension $F$ of $f$ over a polytope $P$ that represents the constraints, and then effectively rounding the fractional solution. Although this approach has been used quite successfully, it has been limited in some important ways. We overcome these limitations as follows. First, we give constant factor approximation algorithms to maximize $F$ over a down-closed polytope $P$ described by an efficient separation oracle. Previously this was known only for monotone functions. For non-monotone functions, a constant factor was known only when the polytope was either the intersection of a fixed number of knapsack constraints or a matroid polytope. Second, we show that contention resolution schemes are an effective way to round a fractional solution, even when $f$ is non-monotone. In particular, contention resolution schemes for different polytopes can be combined to handle the intersection of different constraints. Via LP duality we show that a contention resolution scheme for a constraint is related to the correlation gap of weighted rank functions of the constraint. This leads to an optimal contention resolution scheme for the matroid polytope. Our results provide a broadly applicable framework for maximizing linear and submodular functions subject to independence constraints. We give several illustrative examples. Contention resolution schemes may find other applications.

1 Introduction

The paper develops a general multilinear-relaxation and contention-resolution framework for maximizing non-negative submodular functions under broad downward-closed independence constraints, including non-monotone objectives. It provides constant-factor optimization over solvable down-monotone polytopes, general rounding schemes, and new schemes for diverse packing constraints and matroids.

  • 1 Introduction: Submodular maximization is studied over downward-closed independence families including matroids, knapsacks, and their intersections, with monotone or non-monotone objectives.The function is accessed through a value oracle.
  • 1 Introduction: Combinatorial methods have limited optimality and flexibility for combining different constraint types, motivating multilinear relaxation and polyhedral techniques.The framework relaxes feasible sets to a polytope and rounds a fractional solution to an integral one.
  • 1 Introduction: The paper gives the first constant-factor approximation, up to negligible additive error, for maximizing the multilinear extension over any down-monotone solvable polytope.This result applies to any nonnegative submodular function.
  • 1.2 Contention resolution schemes: Contention resolution schemes round fractional solutions while preserving feasibility and expected submodular value, and schemes for different constraints can be combined for intersections.The schemes retain each independently sampled element with probability at least a controlled fraction of its fractional value.
  • 1.2 Contention resolution schemes: The framework supplies contention-resolution schemes for knapsack, matroid, and several packing constraints, using correlation-gap connections to obtain an optimal scheme for arbitrary matroids.The matroid scheme is monotone and efficiently implementable.
  • 1.1 Maximizing the multilinear extension over a general polytope: For general polytopes, the paper reports a 0.25-approximation algorithm and a 0.309 guarantee relative to the best integer solution in the polytope.The 0.25 result is stated as (0.25−o(1)); the 0.309 algorithm applies to the multilinear extension.

2 Applications

The framework yields CR schemes and approximation algorithms for submodular maximization under several packing and intersection constraints, extending known linear-objective techniques to non-negative submodular functions.

  • Contention resolution schemes: For k-uniform matchoids, combining single-matroid CR schemes yields a (b, (1−e^−b)/b)^k-balanced scheme, including a 2/(e(k+1))-balanced choice.The framework also extends the matroid-polytope scheme to intersections of k matroids.
  • Contention resolution schemes: For a constant number of knapsack constraints, guessing and enumeration effectively provide a (1−ε, 1−ε)-balanced CR scheme for every fixed ε > 0.Other packing schemes can be reinterpreted as CR schemes and then applied to non-negative submodular objectives.
  • Knapsack constraints: 0.309-approximation is achieved for intersections of a fixed number of knapsack constraints, improving previous 0.2 −ε and 0.25 −ε guarantees.The result uses a (1 −ε, 1 −ε)-balanced contention resolution scheme.
  • Matchoids and knapsacks: Ω(1/(k+ℓ))-approximation is obtained for intersections of a k-uniform matchoid and ℓ knapsack constraints, with ℓ fixed.The construction combines balanced CR schemes for matchoids and fixed-number knapsack constraints after separate preprocessing.
  • Sparse packing constraints: Ω(1/(kℓ))-approximation is obtained for intersections of a k-uniform matchoid and an ℓ-sparse knapsack constraint system of width W.This follows by combining CR schemes for matchoids and ℓ-column-sparse packing constraints.
  • Routing applications: A constant factor approximation is obtained for non-negative submodular functions of routed requests in capacitated paths or trees.Previously, an O(1) approximation was known for linear objectives in this setting.

3 Solving the multilinear relaxation for non-negative submodular functions

This section develops constant-factor methods for maximizing the multilinear extension of a non-negative, possibly non-monotone submodular function over a down-monotone solvable polytope. It combines continuous local search, discretization, and repeated local search to obtain a 0.25-approximation, with a restricted variant achieving approximately 0.309 against the best integer solution.

  • Problem setting: The section targets max{F(x) : x ∈P} for non-monotone submodular functions over down-monotone solvable polytopes.The algorithmic framework assumes value-oracle access to f and a separation oracle for P.
  • Continuous local search: Continuous local search seeks a point satisfying the first-order condition (y −x) · ∇F(x) ≤0 for every y ∈P.Submodularity makes F concave along non-negative directions, enabling the local-search analysis despite F not being globally concave.
  • Discretized local search: The discretized algorithm estimates gradients by random sampling and repeatedly replaces a point in a convex combination when an improving direction exceeds the threshold 4δn.With high probability, it terminates in polynomial time.
  • Repeated local search: Two runs of fractional local search yield a 0.25-approximation for multilinear optimization over any solvable down-monotone polytope.The two outputs satisfy 2F(x) + 2F(z) ≥ OPT −10δn, and the additive error can become a multiplicative o(1) term in many settings.
  • Restricted local search: The restricted local-search analysis gives an approximately 0.309-approximation with respect to the optimal integer solution in P.The guarantee does not require a second-stage complementary local search.

4 Contention resolution schemes

This section presents contention resolution schemes as a general rounding framework for fractional solutions under submodular objectives, including non-monotone functions. It shows how pruning, strict schemes, and composition across constraints preserve useful objective guarantees.

  • Basic framework: Contention resolution schemes round independently sampled sets into feasible subsets while supporting submodular-objective guarantees.The framework addresses the failure of independent rounding to preserve the constraints imposed by I.
  • Objective preservation: Monotonicity links contention resolution to submodular maximization because smaller sets provide larger marginal contributions under submodularity.For non-monotone objectives, the analysis uses a pruning procedure to exploit this relationship.
  • Non-monotone rounding: For non-monotone functions, pruning retains elements only when their marginal contribution is positive in a fixed ordering.The rounded output is the CR-scheme output followed by this function-dependent pruning step.
  • Strict schemes: A strict monotone (b, c)-balanced CR scheme gives a corresponding expected-value guarantee without pruning and is oblivious to the underlying submodular function.This can be useful when simultaneously preserving the values of multiple submodular functions.
  • Combining constraints: Combining schemes for intersected constraints produces a scheme with balance parameter ∏i ci, improving on the straightforward union-bound expression.If every element participates in at most k constraints with common balance c, the result is (b, c^k)-balanced.

4.2 Obtaining CR schemes via distributions of deterministic CR schemes

This section characterizes contention resolution schemes through distributions over deterministic mappings and uses LP duality to connect their guarantees to weighted independent-set problems. The resulting framework supports efficient near-optimal schemes when maximum-weight independent sets can be computed.

  • LP formulation: Randomized CR schemes can be viewed as distributions over deterministic feasible mappings, yielding an exponential LP for maximizing the balance parameter.Restricting the mapping family gives the best scheme obtainable from that restricted family.
  • Broader connection: The paper identifies a connection between CR schemes and correlation gap and notes algorithmic consequences for important constraint families such as matroids.This connection is developed through the LP and dual formulations.
  • Characterization: A (b, c)-balanced CR scheme exists exactly when the best per-x LP value is at least c for every x ∈bPI.This is summarized by the infimum characterization in Proposition 4.2.
  • Dual interpretation: The dual LP interprets the guarantee as the worst-case ratio between the expected maximum-weight feasible subset of an independently sampled set and the fractional weighted value.The vector y supplies element weights, while x is the fractional solution.
  • Efficient construction: An ellipsoid-based construction estimates the dual separation objective by sampling independent sets and solving maximum-weight independent-set problems on them.A polynomial-time maximum-weight independent-set algorithm enables efficient randomized schemes approaching the optimum balance parameter within ε.
  • Monotone schemes: The LP framework also handles monotone CR schemes by restricting the deterministic mappings to monotone mappings.Distributions of deterministic monotone schemes remain monotone.

4.3 Connection to correlation gap

This section defines correlation gap as the loss between independent sampling and the best correlated distribution with the same marginals, then relates it exactly to contention-resolution strength. For constraint families, the gap equals the worst weighted-rank-function gap.

  • Correlation gap: For a set function, the correlation gap is the worst-case ratio between its multilinear extension F(x) and concave closure f+(x).The paper normalizes the ratio to lie in [0, 1], with larger values indicating smaller loss.
  • Constraint correlation gap: For an independence family I, the correlation gap is defined over fractional points x ∈PI and non-negative weight vectors y.The associated objective is the weighted rank function of I.
  • CR-scheme equivalence: The correlation gap of I equals the maximum c for which I admits a c-balanced contention resolution scheme.The equality follows by identifying the correlation-gap expression with the dual LP optimum and applying LP duality.
  • Weighted rank functions: The correlation gap of an independence family equals the infimum correlation gap of its weighted rank functions over all non-negative weight vectors.Thus the family-level gap is governed by the worst weighted rank-function case.
  • Proof strategy: The rank-function relationship is established by comparing arbitrary marginal vectors with points in PI and using convex combinations of feasible sets.Monotonicity of the weighted rank function supports restricting the relevant infimum to the polytope.

4.4 Contention resolution for matroids

The section develops contention resolution schemes for matroid polytopes, relating their optimality to weighted rank functions and correlation gaps. It also gives deterministic and efficiently implementable alternatives with quantified balance guarantees.

  • An optimal matroid-polytope scheme follows from the connection between CR schemes and correlation gaps of weighted rank functions.The weighted rank function r_y assigns the maximum weight of an independent subset contained in a set.
  • Theorem 4.8 gives a contention resolution scheme for every matroid polytope.
  • Greedy computation of the weighted rank function makes the corresponding near-optimal CR scheme efficiently implementable.The greedy algorithm processes elements in non-increasing weight order and retains elements while preserving independence.
  • The matroid CR guarantees are asymptotically optimal up to an additive ε, with uniform rank-one matroids providing the matching lower bound.The lower-bound theorem considers a uniform matroid of rank one over n elements.
  • For any matroid M and b ∈ [0, 1], a deterministic (b, 1 − b)-balanced CR scheme exists.The construction recursively orders elements using span probabilities, then retains sampled elements not spanned by earlier retained elements.

4.5 Contention resolution for knapsacks

The section constructs contention resolution schemes for knapsack constraints using size-based ordering and concentration bounds. Enumeration extends the small-item guarantee to general instances and allows combination with other constraints.

  • A monotone (b, 1 − 2b)-balanced CR scheme exists for the knapsack polytope when b ∈ (0, 1/2).It samples items independently and processes sampled items in decreasing size order, accepting each item when feasibility is preserved.
  • When every item size is at most δ, a monotone (1 − ε, 1 − e^−Ω(ε^2/δ))-balanced CR scheme is available.The analysis uses Chernoff bounds to control overflow probabilities for small items.
  • For any constant number k of knapsack constraints, enumeration yields residual instances with (1 − ε, 1 − ε)-balanced schemes for each constraint.The residual construction removes a set T of at most n0 elements before applying the small-item guarantee.
  • Any α-approximate residual solution combined with T is an α(1 − kε)-approximate solution to the original instance.
  • The black-box approach combines knapsack constraints arbitrarily with other constraint types, but enumeration increases running time by an O(n^n0) factor.

4.6 Sparse packing systems

The section treats k-sparse packing systems as packing constraints in which each element participates in at most k inequalities. It gives contention resolution schemes whose balance depends on sparsity and system width.

  • A k-sparse packing system is one where each column of A has at most k nonzero entries.Thus each element participates in at most k linear constraints.
  • A monotone (b, 1 − 2kb)-balanced CR scheme is obtained for k-sparse packing systems.The scheme samples independently, marks elements violating constraints for deletion, and outputs the remaining sampled elements.
  • In the basic analysis, each element is removed with probability at most 2b for each constraint in which it participates, hence at most 2kb overall.The overall bound follows by a union bound across the at most k participating constraints.
  • For systems of width W ≥ 2, a monotone (b, 1 − k(2eb)^(W−1))-balanced CR scheme is available.The width parameter controls the maximum normalized coefficient in each constraint.
  • The width-sensitive analysis bounds removal by at most (2eb)^(W−1) for each participating constraint.

4.7 UFP in paths and trees

This section applies contention resolution to unsplittable flow routing on capacitated paths and trees, extending the framework to non-negative submodular request weights and general demands.

  • Problem: Routable sets are request subsets whose fixed paths respect every tree-edge capacity.Each request contributes its demand along the unique path between its endpoints.
  • Problem: The section targets maximizing a non-negative submodular function over routable requests, extending prior work on linear weights.The resulting contention resolution scheme implies a constant-factor approximation through the paper’s framework.
  • Unit demands: The unit-demand scheme samples requests independently, processes them by increasing depth, and accepts a request only when the partial routing remains feasible.This greedy contention-resolution procedure rejects requests that would exceed an edge capacity.
  • Unit demands: For a fixed request, edge-capacity overload events are bounded using independent sampling and Chernoff bounds, followed by a union bound along its path.The analysis accounts for correlated rejection events across edges.
  • Unit demands: 2eb bounds the probability that a sampled request is rejected on a tree path, conditioned on its inclusion in the random set.The bound combines rejection probabilities on the two path segments around the least common ancestor.
  • General demands: Under no-bottleneck demands, grouping and scaling convert a unit-demand scheme into a general-demand scheme with parameters (b/6, (1 −b′)/2).Without the no-bottleneck assumption, the LP can have an Ω(n) integrality gap even on paths.

4.8 Column-restricted packing constraints

This section develops a grouping-and-scaling conversion for column-restricted packing constraints, transferring contention resolution guarantees from 0-1 systems to bounded-demand systems.

  • Setup: A column-restricted packing integer program scales each nonzero entry in a 0-1 matrix column by that column’s demand.The resulting constraints have the form A[d]x ≤ b with binary decisions.
  • Conversion theorem: Theorem 4.20 converts a monotone (β, 1 −β′) scheme for Ax ≤b into a monotone (β/6, (1 −β′)/2) scheme for A[d]x ≤b under dmax ≤bmin.The conversion applies for integer right-hand sides and non-negative column demands.
  • Construction: The conversion groups columns by geometrically decreasing demand ranges, treating the largest-demand group separately from smaller groups.Each restricted fractional vector is scaled and paired with rounded row capacities.
  • Feasibility: Feasible integral solutions for each grouped 0-1 system remain feasible for the original demand-scaled system.This feasibility statement is formalized by Lemma 4.21.
  • Construction: The scheme independently runs the base contention-resolution procedure on each group and randomly selects either the large-demand output or the union of small-demand outputs.The random selection accounts for the additional loss in the balanced parameter.
  • Special cases: When all demands are small or all are large, the second-stage random choice is unnecessary, preserving the stronger balance parameter 1 −β′.In these cases the scheme is (β/6, 1 −β′)-balanced.

A Approximation for general polytopes

This appendix gives a continuous local-search algorithm for approximately maximizing the multilinear extension over a general solvable polytope, assuming the polytope contains a sufficiently small box point.

  • Scope: The appendix extends multilinear-extension approximation beyond down-monotone polytopes, although it reports no concrete applications for this general-polytope result.The result generalizes a matroid-base-polytope result while losing a factor of four.
  • Algorithm: The algorithm requires P ∩[0, t]^N to be nonempty and searches within the larger region P ∩[0, (1+t)/2]^N.The larger search region is needed for the analysis.
  • Algorithm: Algorithm A.1 initializes a feasible point, follows improving directions y −x based on the gradient of F, and stops when no improving feasible point exists.The improving point can be found by linear programming.
  • Guarantee: Theorem A.2 states that Algorithm A.1 approximates max{F(x) : x ∈P} within a factor of 1
  • Analysis: The analysis combines the current point with an optimum through a midpoint construction and uses concavity of F in positive directions.The constructed comparison point remains inside the enlarged search region.

Proof of Theorem 4.1

This proof establishes that a balanced contention resolution scheme preserves a corresponding fraction of the multilinear objective’s expected marginal gains.

  • Proof strategy: The proof conditions on the sampled set R first and then takes expectation over R to analyze the rounded set I.
  • Marginal analysis: Only elements included in R can enter I, so the expected marginal contribution of each element is restricted to the event i ∈R.
  • Correlation step: Monotonicity of the scheme and submodularity of f make the survival probability and marginal value positively correlated under the conditioned product distribution.The proof invokes the FKG inequality for this correlation.
  • Conclusion: A (b, c)-balanced scheme therefore guarantees each rounded marginal at least c times the corresponding sampled marginal in expectation.

Proof of Lemma 4.10

The proof of Lemma 4.10 uses Lemma B.2, a generalized submodularity inequality, to compare random-set constructions with the multilinear extension. It handles two cases based on the number of sets in a basic concave-closure solution and bounds the resulting probabilities through concavity and arithmetic-geometric mean arguments.

  • Auxiliary lemma: Lemma B.2 generalizes an earlier submodularity lemma and provides two statements, the stronger of which implies Lemma 4.10.The proof follows the earlier lemma’s technique and applies the stronger statement to the constructed random sets.
  • Inequality proof: The key inequality is proved by ordering the set values, reducing to binary-valued cases, and splitting into r < t and r ≥ t.Each case uses arithmetic-geometric mean bounds and concavity of φr or φr−1; the proof then concludes Lemma 4.10.
  • Case split: A basic solution to the concave-closure linear program uses at most n + 1 sets, yielding cases m ≤ n and m = n + 1.The bound follows because the linear program has n + 1 constraints apart from nonnegativity constraints.
  • Case m ≤ n: When m ≤ n, the proof shows the constructed random set is dominated by R(bp), so F(bp) ≥ E[f(A)].The comparison uses independent inclusion probabilities and completes the first case through monotonicity and concavity arguments.
  • Case m = n + 1: When m = n + 1, one set is covered by the others; probabilities are modified using an index with minimum bαs before applying Lemma B.2.The proof again compares the constructed set with R(bp), treating elements inside and outside the covered set separately.

C Details in constructing CR schemes via the ellipsoid algorithm

This section constructs CR schemes through approximate probability estimates and a weak separation oracle for the dual program. Monte Carlo estimates support the oracle, while the ellipsoid method and duality produce near-optimal primal solutions.

  • Probability estimates: The construction begins by estimating each probability qi,φ within ±ǫxi with high probability using polynomially many samples.The estimate factors as qi,φ = xi · Pr[R \ {i} is good], and the remaining probability is approximated by Monte Carlo sampling.
  • Approximate coefficients: Pessimistic estimates eqi,φ ≤ qi,φ preserve feasibility while lowering the optimal value of the associated linear program.The estimates can be obtained with high probability because the ellipsoid algorithm uses only polynomially many estimates.
  • Weak separation oracle: The weak separation oracle either returns a nearly feasible dual solution or a separating hyperplane generated by a contention-resolution scheme.The scheme is selected to maximize the weighted expression Σi∈N eqi,φyi.
  • Ellipsoid solution: The ellipsoid method obtains a feasible dual solution with value at most µ* + 2ǫ.Feasibility also gives µ* ≤ µ, placing the computed value within 2ǫ of the optimum.
  • Recovering the primal solution: Restricting the dual to constraints generated during the ellipsoid run yields a polynomial-size program whose dual solution is feasible for the original primal program.Strong duality transfers the near-optimality guarantee from the restricted dual formulation to the returned primal solution.
Loading 1105.4593v5…