Maximizing Non-monotone Submodular Functions
From MaRDI portal
Publication:3096096
DOI10.1137/090779346zbMath1230.90198WikidataQ101125896 ScholiaQ101125896MaRDI QIDQ3096096
Jan Vondrák, Uriel Feige, Vahab S. Mirrokni
Publication date: 7 November 2011
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/090779346
combinatorial optimization; approximation algorithms; local search algorithms; submodular functions; submodular function maximization; information-theoretic lower bounds
90C35: Programming involving graphs or networks
90C59: Approximation methods and heuristics in mathematical programming
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W25: Approximation algorithms
Related Items
A Polynomial Algorithm for a Class of 0–1 Fractional Programming Problems Involving Composite Functions, with an Application to Additive Clustering, An FPTAS for optimizing a class of low-rank functions over a polytope, Maximizing non-monotone submodular set functions subject to different constraints: combined algorithms, Simultaneous approximation of multi-criteria submodular function maximization, A framework of discrete DC programming by discrete convex analysis, Maximizing a class of submodular utility functions with constraints, New performance guarantees for the greedy maximization of submodular set functions, Optimization with uniform size queries, Classes of submodular constraints expressible by graph cuts, Simultaneous selection, The expressive power of binary submodular functions, FPT approximation schemes for maximizing submodular functions, Maximizing monotone submodular functions over the integer lattice, Approximation algorithms for connected maximum cut and related problems, Informative path planning as a maximum traveling salesman problem with submodular rewards, A tight analysis of the submodular-supermodular procedure, Oblivious algorithms for the maximum directed cut problem, Inequalities on submodular functions via term rewriting, On the efficiency of influence-and-exploit strategies for revenue maximization under positive externalities, Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas, Bounds on Double-Sided Myopic Algorithms for Unconstrained Non-monotoneSubmodular Maximization, Nonmonotone Submodular Maximization via a Structural Continuous Greedy Algorithm, Improved Competitive Ratios for Submodular Secretary Problems (Extended Abstract), The Expressive Power of Binary Submodular Functions, Robust Monotone Submodular Function Maximization, A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization, Maximizing Symmetric Submodular Functions
