Maximization of submodular functions: theory and enumeration algorithms

DOI10.1016/j.ejor.2008.08.022zbMath1163.90770OpenAlexW2490232925MaRDI QIDQ1027590

Boris I. Goldengorin

Publication date: 30 June 2009

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2008.08.022

zbMATH Keywords

maximizationenumeration algorithmssubmodular functions

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Related Items (9)

Multi-level facility location as the maximization of a submodular set function ⋮ Maximizing a non-decreasing non-submodular function subject to various types of constraints ⋮ Hub Location as the Minimization of a Supermodular Set Function ⋮ A fast and deterministic algorithm for knapsack-constrained monotone DR-submodular maximization over an integer lattice ⋮ Constraint generation approaches for submodular function maximization leveraging graph properties ⋮ Formulations and Approximation Algorithms for Multilevel Uncapacitated Facility Location ⋮ Maximizing DR-submodular+supermodular functions on the integer lattice subject to a cardinality constraint ⋮ Maximization problems of balancing submodular relevance and supermodular diversity ⋮ Adaptive seeding for profit maximization in social networks

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimum algorithm for maximization of submodular functions
• Supermodularity and preferences
• Maximizing a submodular function by integer programming: Polyhedral results for the quadratic case
• An improved branch \& bound method for the uncapacitated competitive location problem
• Lagrangean heuristics for location problems
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• Pipage rounding: a new method of constructing algorithms with proven performance guarantee
• A multilevel search algorithm for the maximization of submodular functions applied to the quadratic cost partition problem
• Constrained Maximum-Entropy Sampling
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• An Accelerated Sequential Algorithm for ProducingD-Optimal Designs
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• A cost function property for plant location problems
• Comments on the note of Frieze
• Optimal Location of Plants
• An analysis of approximations for maximizing submodular set functions—I
• Best Algorithms for Approximating the Maximum of a Submodular Set Function
• An Exact Algorithm for Maximum Entropy Sampling
• The Data-Correcting Algorithm for the Minimization of Supermodular Functions
• On the Set-Covering Problem

This page was built for publication: Maximization of submodular functions: theory and enumeration algorithms