Inequalities on submodular functions via term rewriting

DOI10.1016/J.IPL.2013.03.018MaRDI QIDQ2444736zbMATH OpenOpenAlexFDO

Authors Yuval Filmus

Publication date 11 April 2014

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2013.03.018

zbMATH Keywords

analysis of algorithmsinequalitieslocal searchsubmodularity

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42) Analysis of algorithms (68W40) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• On the subdifferential of a submodular function
• scientific article; zbMATH DE number 3898611
• scientific article; zbMATH DE number 4099306
• scientific article; zbMATH DE number 3904328
• Submodular functions: optimization and approximation
• Cheeger inequalities for submodular transformations
• Extremality of submodular functions
• On submodular function minimization
• Submodular function minimization and maximization in discrete convex analysis
• Complexity and approximations for submodular minimization problems on two variables per inequality constraints

Cites work

• A threshold of ln n for approximating set cover
• An analysis of approximations for maximizing submodular set functions—I
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Comments on bases in dependence structures
• Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
• scientific article; zbMATH DE number 3904328 (Why is no real title available?)
• scientific article; zbMATH DE number 3635849 (Why is no real title available?)
• scientific article; zbMATH DE number 1323125 (Why is no real title available?)
• scientific article; zbMATH DE number 3422402 (Why is no real title available?)
• Induced Matroids
• Matroid matching: the power of local search
• Maximizing a monotone submodular function subject to a matroid constraint
• Maximizing Non-monotone Submodular Functions
• Maximizing nonmonotone submodular functions under matroid or knapsack constraints
• Submodular functions and optimization.
• Symmetry and Approximability of Submodular Maximization Problems
• The power of local search: maximum coverage over a matroid

Cited in

(1)

• Inferring range of information diffusion based on historical frequent items

This page was built for publication: Inequalities on submodular functions via term rewriting

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