A note on the implications of approximate submodularity in discrete optimization

DOI10.1007/S11590-022-01890-WMaRDI QIDQ2678995zbMATH OpenOpenAlexFDO

Authors Temitayo Ajayi, Taewoo Lee, Andrew J. Schaefer

Publication date 18 January 2023

Published in Optimization Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11590-022-01890-w

zbMATH Keywords

approximate submodularityset function extensionsvalid inequalities

Mathematics Subject Classification ID

Integer programming (90C10) Combinatorial optimization (90C27)

Recommendations

• Submodular functions: optimization and approximation
• Approximations for Monotone and Nonmonotone Submodular Maximization with Knapsack Constraints
• Submodular function minimization and maximization in discrete convex analysis
• Maximizing submodular set functions subject to multiple linear constraints
• Submodular functions: learnability, structure, and optimization

Cites work

• Discrete convex analysis
• Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
• Facet of regular 0–1 polytopes
• Facets of the knapsack polytope
• Functional analysis in asymmetric normed spaces
• scientific article; zbMATH DE number 1667417 (Why is no real title available?)
• scientific article; zbMATH DE number 4202014 (Why is no real title available?)
• scientific article; zbMATH DE number 3904328 (Why is no real title available?)
• scientific article; zbMATH DE number 44281 (Why is no real title available?)
• scientific article; zbMATH DE number 193411 (Why is no real title available?)
• scientific article; zbMATH DE number 3422402 (Why is no real title available?)
• Is submodularity testable?
• Learning with submodular functions: a convex optimization perspective
• Polymatroids and mean-risk minimization in discrete optimization
• Reducibility among combinatorial problems
• Strong formulations for conic quadratic optimization with indicator variables
• Submodular function minimization and polarity
• Submodular functions and electrical networks
• Submodularity in Conic Quadratic Mixed 0–1 Optimization
• The submodular knapsack polytope
• Valid inequalities for mixed integer linear programs

Cited in

(4)

• On additive approximate submodularity
• The Methods for Approximation of Principal Points for Binary Distributions on the Basis of Submodularity
• Near-optimal Approximate Discrete and Continuous Submodular Function Minimization
• Note on pseudolattices, lattices and submodular linear programs

Describes a project that uses

Uses Software

• Gurobi

This page was built for publication: A note on the implications of approximate submodularity in discrete optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2678995)