Source-linked AI summary
Constrained Submodular Maximization via a Non-symmetric Technique
Niv Buchbinder, Moran Feldman
TL;DR
Improving many submodular maximization problems calls for better algorithms for optimizing the multilinear relaxation, particularly in the non-monotone setting over down-closed solvable polytopes. The paper combines fractional local search with an aided Measured Continuous Greedy algorithm. It guarantees 0.385·f(OPT) in polynomial time for non-negative submodular functions over those polytopes.
Problem
Further improvements for many submodular maximization problems depend on better algorithms for the multilinear relaxation, with the general non-monotone setting considered over solvable down-closed polytopes.
Source: §1 · p. 2, §1.1 · p. 3Method
The algorithm runs fractional local search, then uses its output to parameterize an aided Measured Continuous Greedy algorithm, and returns one of the two outputs probabilistically.
Source: §3 · pp. 5–6Results
0.385·f(OPT) is the expected-value guarantee achieved by the algorithm for non-negative submodular functions over solvable down-closed polytopes.
Source: §1.2 · p. 4, §3 · p. 7Takeaways & Limitations
The paper establishes a polynomial-time 0.385 guarantee for optimizing the multilinear relaxation in the stated constrained setting.
Source: §1.2 · p. 4The algorithmic setting assumes value-oracle access to f, with queries returning f(S) for a given set S.
Source: §2 · p. 5
Abstract
from arXiv · showhide
The study of combinatorial optimization problems with a submodular objective has attracted much attention in recent years. Such problems are important in both theory and practice because their objective functions are very general. Obtaining further improvements for many submodular maximization problems boils down to finding better algorithms for optimizing a relaxation of them known as the multilinear extension. In this work we present an algorithm for optimizing the multilinear relaxation whose guarantee improves over the guarantee of the best previous algorithm (which was given by Ene and Nguyen (2016)). Moreover, our algorithm is based on a new technique which is, arguably, simpler and more natural for the problem at hand. In a nutshell, previous algorithms for this problem rely on symmetry properties which are natural only in the absence of a constraint. Our technique avoids the need to resort to such properties, and thus, seems to be a better fit for constrained problems.
1 Introduction
Submodular maximization covers many combinatorial problems, and improving them often depends on finding better fractional solutions to the multilinear relaxation. This paper presents a polynomial-time algorithm that guarantees 0.385·f(OPT) for non-negative submodular functions over solvable down-closed polytopes, using a technique the authors argue is better suited to constraints.
1 Introduction
- Many submodular maximization problems can benefit from improved multilinear-relaxation optimization because available rounding procedures cover constraints such as knapsack, matroid, and matching intersections.The paper identifies improving the fractional solution as the remaining route to further gains for many such problems.Source: §1 · p. 2
1.1 Maximizing the Multilinear Relaxation
- The multilinear relaxation replaces the feasible-set constraint with a polytope and the set function with an extension; its objective is the expected value over an independently sampled random subset.Each element u is included in the random subset with probability x_u.Source: §1.1 · pp. 2–3
- For non-monotone objectives, the general setting requires non-negative functions and solvable down-closed polytopes; no constant-factor guarantee is possible for solvable polytopes that are not down-closed.Before this work, the best general guarantee was 0.372, while the cited inapproximability bound was 0.478 for a partition-matroid polytope.Source: §1.1 · p. 3
1.2 Our Contribution
- The 0.385 guarantee improves on Ene and Nguyen’s 0.372 guarantee for every down-closed solvable polytope, while the paper describes the numerical gain as relatively small.The authors characterize their technique as different and cleaner, and argue it may yield further improvements.Source: §1.1 · p. 3, §1.2 · p. 4
- 0.385·f(OPT) is guaranteed by a polynomial-time algorithm for non-negative submodular functions over solvable down-closed polytopes.The guarantee applies to the multilinear extension over the stated polytope.Source: §1.2 · p. 4
- The algorithm replaces the symmetry-based unconstrained technique used in prior improvements with local search that guides Measured Continuous Greedy when its output is poor.The paper notes that the symmetry exploited by unconstrained maximization breaks when a constraint is introduced.Source: §1.2 · p. 4
2 Preliminaries
The preliminaries introduce extensions and notation used in the analysis, then state assumptions about feasible singleton elements and access to the objective function.
2 Preliminaries
- The multilinear extension is at least the Lovász extension at every vector in [0, 1]^N.The paper uses this known relation in its analysis.Source: §2 · p. 5
- The analysis uses coordinate-wise maximum, minimum, and product, characteristic vectors, and the partial derivative of the multilinear extension.The paper notes that the derivative observation follows because the extension is multilinear.Source: §2 · p. 5
- The paper assumes every singleton vector is feasible and uses a value oracle that returns f(S) for a queried set S.Elements whose singleton vectors are infeasible can be removed, and constant-size instances can be solved in constant time.Source: §2 · p. 5
3 Main Algorithm
The main algorithm combines fractional local search with an auxiliary algorithm that uses the first output to guide Measured Continuous Greedy. With the stated parameters, it achieves an expected value of at least 0.385 · f(OPT).
3 Main Algorithm
- The first component returns a vector in P that, with high probability, satisfies the local-search inequality for every y in P.The bound follows from the fractional local-search results cited from Chekuri et al..Source: §3 · p. 6
- The auxiliary component guarantees E[F(x)] ≥ e^(ts−1) · [(2 − ts − e^(−ts) − o(1)) · f(OPT) − (1 − e^(−ts)) · F(z ∧ 1_OPT].Its output is a vector in P, with z supplied by the first component.Source: §3 · p. 6
- The algorithm runs fractional local search, then uses its output as z for the auxiliary algorithm, and randomizes between the two resulting vectors.It returns the first vector with probability p and the second otherwise.Source: §3 · p. 6
- 0.385 · f(OPT) is the expected-value guarantee when the algorithm uses ts = 0.372 and p = 0.23.The parameter optimization gives a lower bound of 0.3856 · f(OPT).Source: §3 · pp. 7–8
4 Aided Measured Continuous Greedy
Aided Measured Continuous Greedy uses a set Z to guide the growth of a fractional solution, initially excluding elements of Z and later switching to standard Measured Continuous Greedy. Its guarantee is then extended from integral sets to fractional inputs by sampling.
4 Aided Measured Continuous Greedy
- The section first proves a simplified version for integral inputs and then shows that it implies the original theorem for fractional z.The proof sketch uses direct access to F and continuous time; Appendix A gives a formal proof using known techniques.Source: §4 · pp. 8–9
- E[F(x)] ≥ e^(ts−1) · [(2 − ts − e^(−ts) − o(1)) · f(OPT) − (1 − e^(−ts)) · f(Z ∩ OPT)].The theorem gives a polynomial-time algorithm producing x ∈ P for any set Z and ts ∈ [0,1].Source: §4 · p. 8
- The guarantee for fractional z follows by sampling Z from R(z), applying the set-based guarantee, and taking expectation over Z.The expected term f(Z ∩ OPT) equals F(z ∧ 1_OPT).Source: §4 · p. 8
- During [0, ts), the algorithm assigns elements of Z negative marginal profits; from ts onward, it grows the solution as Measured Continuous Greedy does.The switch time ts separates the two growth rules.Source: §4 · p. 9
A A Formal Proof of Theorem 4.1
This section provides a formal proof of Theorem 4.1 using a discrete variant of Algorithm 2 and techniques addressing issues in the Section 4 proof. It closes the induction for g(t), derives an expectation lower bound, and combines it with Corollary A.2 to conclude the theorem.
A Formal Proof of Theorem 4.1
- Algorithm 3 keeps y(t) in [0, 1]^N and outputs a vector in P, using the cube bound and the down-closedness and convexity of P.The proof establishes feasibility by expressing the output through a convex combination and applying down-closedness.Source: A A Formal Proof of Theorem 4.1 · p. 16
- Corollary A.4 states that event A has probability at least 1 − n^-1; the cited passage does not specify A, and the estimator averages independent samples.Each estimate averages r = ⌈48n6 ln(2n)⌉ independent samples of R(y(t)).Source: A A Formal Proof of Theorem 4.1 · pp. 15–16
- Given event A, each update increases F(y(t)) by at least δt times the gain from adjoining OPT′_t, minus O(n^-1δt) · f(OPT).OPT′_t is OPT \ Z before t_s and OPT thereafter.Source: A A Formal Proof of Theorem 4.1 · pp. 17–18
- Given A, the recursive lower-bound sequence g(t) stays within O(n^-1) · t · f(OPT) of F(y(t)); h1 and h2 provide lower bounds on g before and after t_s.The two bounds apply on [0, t_s] and [t_s, 1], respectively.Source: A A Formal Proof of Theorem 4.1 · pp. 20–21
A A Formal Proof of Theorem 4.1
- The induction step bounds h2(t + δt) by (1 − δt)g(t) + δt·e^(−t)·A, which equals g(t + δt).The preceding lemmata provide the closed-form lower bound on g(t).Source: A A Formal Proof of Theorem 4.1 · p. 22
- E[F(y(1))] ≥ ets−1 ·[(2−ts−e−ts−O(n−1))·f(OPT)−(1−e−ts)·f(Z∩OPT)−(2−ts−2e−ts)·f(Z∪OPT)] in Corollary A.14.This is the stated closed-form lower bound on the expected value.Source: A A Formal Proof of Theorem 4.1 · p. 22
- Since F(y(1)) is non-negative and Pr[A] ≥ 1 − n^−1, the conditional bound yields the expectation bound, and Corollaries A.2 and A.14 imply Theorem 4.1.The probability bound is given by Corollary A.4.Source: A A Formal Proof of Theorem 4.1 · p. 23