Submodular function maximization in parallel via the multilinear relaxation

Chandra Chekuri, Kent Quanrud

Research output: Contribution to conferencePaperpeer-review


Balkanski and Singer [4] recently initiated the study of adaptivity (or parallelism) for constrained submodular function maximization, and studied the setting of a cardinality constraint. Subsequent improvements for this problem by Balkanski, Rubinstein, and Singer [6] and Ene and Nguyen [21] resulted in a near-optimal (1−1/e−)-approximation in O(log n/2) rounds of adaptivity. Partly motivated by the goal of extending these results to more general constraints, we describe parallel algorithms for approximately maximizing the multilinear relaxation of a monotone submodular function subject to packing constraints. Formally our problem is to maximize F(x) over x ∈ [0,1]n subject to Ax ≤ 1 where F is the multilinear relaxation of a monotone submodular function. Our algorithm achieves a near-optimal (1 − 1/e − )-approximation in O(log2 mlog n/4) rounds where n is the cardinality of the ground set and m is the number of packing constraints. For many constraints of interest, the resulting fractional solution can be rounded via known randomized rounding schemes that are oblivious to the specific submodular function. We thus derive randomized algorithms with poly-logarithmic adaptivity for a number of constraints including partition and laminar matroids, matchings, knapsack constraints, and their intersections. Our algorithm takes a continuous view point and combines several ideas ranging from the continuous greedy algorithm of [38, 13], its adaptation to the MWU framework for packing constraints [20], and parallel algorithms for packing LPs [31, 41]. For the basic setting of cardinality constraints, this viewpoint gives rise to an alternative, simple to understand algorithm that matches recent results [6, 21]. Our algorithm to solve the multilinear relaxation is deterministic if it is given access to a value oracle for the multilinear extension and its gradient; this is possible in some interesting cases such as the coverage function of an explicitly given set system.

Original languageEnglish (US)
Number of pages20
StatePublished - 2019
Event30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019 - San Diego, United States
Duration: Jan 6 2019Jan 9 2019


Conference30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019
Country/TerritoryUnited States
CitySan Diego

ASJC Scopus subject areas

  • Software
  • General Mathematics


Dive into the research topics of 'Submodular function maximization in parallel via the multilinear relaxation'. Together they form a unique fingerprint.

Cite this