Maximizing Non-monotone Submodular Functions
From MaRDI portal
Publication:3096096
DOI10.1137/090779346zbMath1230.90198OpenAlexW2053381548WikidataQ101125896 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 optimizationapproximation algorithmslocal search algorithmssubmodular functionssubmodular function maximizationinformation-theoretic lower bounds
Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Related Items
Deterministic \(\boldsymbol{(\unicode{x00BD}+\varepsilon)}\) -Approximation for Submodular Maximization over a Matroid, Approximation algorithm of maximizing non-monotone non-submodular functions under knapsack constraint, A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization, Maximizing Symmetric Submodular Functions, Fast Distributed Approximation for Max-Cut, The Expressive Power of Binary Submodular Functions, Streaming submodular maximization under differential privacy noise, Measured continuous greedy with differential privacy, Robust Monotone Submodular Function Maximization, Submodular Functions: Learnability, Structure, and Optimization, Unnamed Item, Unnamed Item, Online Submodular Welfare Maximization: Greedy Beats 1/2 in Random Order, Every finite distributive lattice is isomorphic to the minimizer set of an \(M^\natural \)-concave set function, A 1/2-approximation algorithm for maximizing a non-monotone weak-submodular function on a bounded integer lattice, An FPTAS for optimizing a class of low-rank functions over a polytope, Classes of submodular constraints expressible by graph cuts, Bounds on Double-Sided Myopic Algorithms for Unconstrained Non-monotoneSubmodular Maximization, Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint, FPT approximation schemes for maximizing submodular functions, Information coverage maximization for multiple products in social networks, Submodular functions: from discrete to continuous domains, On additive approximate submodularity, A fast and deterministic algorithm for knapsack-constrained monotone DR-submodular maximization over an integer lattice, Submodular maximization over data streams with differential privacy noise, Efficient Optimization of Partition Scan Statistics via the Consecutive Partitions Property, Maximizing non-monotone submodular set functions subject to different constraints: combined algorithms, Evolutionary algorithms and submodular functions: benefits of heavy-tailed mutations, Constrained Submodular Maximization via a Nonsymmetric Technique, Submodular Maximization Through the Lens of Linear Programming, A single factor approximation ratio algorithm for DR-submodular maximization on integer lattice beyond non-negativity and monotonicity, Unnamed Item, On maximizing sums of non-monotone submodular and linear functions, Algorithms for cardinality-constrained monotone DR-submodular maximization with low adaptivity and query complexity, Constraint generation approaches for submodular function maximization leveraging graph properties, A binary search double greedy algorithm for non-monotone DR-submodular maximization, Bicriteria algorithms for maximizing the difference between submodular function and linear function under noise, Unnamed Item, Simultaneous selection, A fast algorithm for maximizing a non-monotone DR-submodular integer lattice function, A simple deterministic algorithm for symmetric submodular maximization subject to a knapsack constraint, Unnamed Item, Profit maximization in social networks and non-monotone DR-submodular maximization, Inequalities on submodular functions via term rewriting, Stochastic block-coordinate gradient projection algorithms for submodular maximization, On the efficiency of influence-and-exploit strategies for revenue maximization under positive externalities, A Survey on Double Greedy Algorithms for Maximizing Non-monotone Submodular Functions, Simultaneous approximation of multi-criteria submodular function maximization, Submodular Optimization with Contention Resolution Extensions., The Submodular Secretary Problem Goes Linear, A framework of discrete DC programming by discrete convex analysis, Deterministic approximation algorithm for submodular maximization subject to a matroid constraint, Nonmonotone Submodular Maximization via a Structural Continuous Greedy Algorithm, Maximizing a class of submodular utility functions with constraints, New performance guarantees for the greedy maximization of submodular set functions, An approximation algorithm for a competitive facility location problem with network effects, Optimization with uniform size queries, The expressive power of binary submodular functions, Non-monotone submodular function maximization under \(k\)-system constraint, Unnamed Item, Blocking rumor by cut, Viral marketing of online game by DS decomposition in social networks, Profit maximization problem with coupons in social networks, Monotone submodular maximization over the bounded integer lattice with cardinality constraints, Sequence submodular maximization meets streaming, Approximation guarantees for parallelized maximization of monotone non-submodular function with a cardinality constraint, Fast algorithms for maximizing monotone nonsubmodular functions, Approximation guarantees for parallelized maximization of monotone non-submodular function with a cardinality constraint, Robust monotone submodular function maximization, Maximizing monotone submodular functions over the integer lattice, Posimodular function optimization, Online submodular maximization: beating 1/2 made simple, A fast double greedy algorithm for non-monotone DR-submodular function maximization, Generalized budgeted submodular set function maximization, Finding Submodularity Hidden in Symmetric Difference, Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas, Online Submodular Maximization with Preemption, Approximation algorithms for connected maximum cut and related problems, Improved Competitive Ratios for Submodular Secretary Problems (Extended Abstract), Set function optimization, Computing a small agreeable set of indivisible items, Maximizing submodular or monotone approximately submodular functions by multi-objective evolutionary algorithms, Private non-monotone submodular maximization, Improved Randomized Algorithm for k-Submodular Function Maximization, Online Contention Resolution Schemes with Applications to Bayesian Selection Problems, An adaptive algorithm for maximization of non-submodular function with a matroid constraint, Submodular maximization of concave utility functions composed with a set-union operator with applications to maximal covering location problems, Submodular function minimization and polarity, k-Submodular maximization with two kinds of constraints, Unnamed Item, Unnamed Item, 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, Budget-Feasible Mechanism Design for Non-monotone Submodular Objectives: Offline and Online, An Optimal Streaming Algorithm for Submodular Maximization with a Cardinality Constraint, Two approximation algorithms for maximizing nonnegative weakly monotonic set functions, Tight Approximation for Unconstrained XOS Maximization, A Polynomial Algorithm for a Class of 0–1 Fractional Programming Problems Involving Composite Functions, with an Application to Additive Clustering, New approximations and hardness results for submodular partitioning problems, An optimal monotone contention resolution scheme for bipartite matchings via a polyhedral viewpoint
