Submodular functions: from discrete to continuous domains

DOI10.1007/S10107-018-1248-6zbMath1423.90174arXiv1511.00394OpenAlexW2963719189MaRDI QIDQ2414912

Francis Bach

Publication date: 17 May 2019

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1511.00394

zbMATH Keywords

submodularityoptimal transportcontinuous optimization

Mathematics Subject Classification ID

Convex programming (90C25) Combinatorial optimization (90C27)

Related Items (17)

Lifting the Convex Conjugate in Lagrangian Relaxations: A Tractable Approach for Continuous Markov Random Fields ⋮ A 1/2-approximation algorithm for maximizing a non-monotone weak-submodular function on a bounded integer lattice ⋮ The equivalence of optimal perspective formulation and Shor's SDP for quadratic programs with indicator variables ⋮ Distributionally Robust Linear and Discrete Optimization with Marginals ⋮ \(2 \times 2\)-convexifications for convex quadratic optimization with indicator variables ⋮ Equilibrium of individual concern-critical influence maximization in virtual and real blending network ⋮ The Frank-Wolfe algorithm: a short introduction ⋮ On the convex hull of convex quadratic optimization problems with indicators ⋮ Supermodularity and valid inequalities for quadratic optimization with indicators ⋮ Linear-step solvability of some folded concave and singly-parametric sparse optimization problems ⋮ Stochastic block-coordinate gradient projection algorithms for submodular maximization ⋮ A Survey on Double Greedy Algorithms for Maximizing Non-monotone Submodular Functions ⋮ Stochastic Conditional Gradient++: (Non)Convex Minimization and Continuous Submodular Maximization ⋮ Dependence in elliptical partial correlation graphs ⋮ Non-convex isotonic regression via the Myersonian approach ⋮ Robust budget allocation via continuous submodular functions ⋮ Stochastic Variance Reduction for DR-Submodular Maximization

Uses Software

• PMTK

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Submodular spectral functions of principal submatrices of a Hermitian matrix, extensions and applications
• Iterative hard thresholding for compressed sensing
• Active set algorithms for isotonic regression; a unifying framework
• Convex analysis and nonlinear optimization. Theory and examples.
• On total variation minimization and surface evolution using parametric maximum flows
• A faster strongly polynomial time algorithm for submodular function minimization
• Classes of orderings of measures and related correlation inequalities. I. Multivariate totally positive distributions
• Two algorithms for maximizing a separable concave function over a polymatroid feasible region
• Nondifferentiable optimization and polynomial problems
• Exact solutions of some nonconvex quadratic optimization problems via SDP and SOCP relaxa\-tions
• Notes on L-/M-convex functions and the separation theorems
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• The smooth-Lasso and other \(\ell _{1}+\ell _{2}\)-penalized methods
• Optimal transport for applied mathematicians. Calculus of variations, PDEs, and modeling
• Submodular functions and optimization.
• Theory of capacities
• Duality Between Subgradient and Conditional Gradient Methods
• Convex Optimization in Infinite Dimensional Spaces
• Global Solutions of Variational Models with Convex Regularization
• Maximizing Non-monotone Submodular Functions
• A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
• Approximate Primal Solutions and Rate Analysis for Dual Subgradient Methods
• Finding the nearest point in A polytope
• An analysis of approximations for maximizing submodular set functions—I
• Minimizing a Submodular Function on a Lattice
• Monotone Comparative Statics
• Variable Selection via Nonconcave Penalized Likelihood and its Oracle Properties
• Learning with Submodular Functions: A Convex Optimization Perspective
• An Inequality for Rearrangements
• Optimal Transport

This page was built for publication: Submodular functions: from discrete to continuous domains