Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature
From MaRDI portal
Publication:4595963
DOI10.1287/moor.2016.0842zbMath1386.90129arXiv1311.4728OpenAlexW3138381145MaRDI QIDQ4595963
Justin Ward, M. I. Sviridenko, Jan Vondrák
Publication date: 7 December 2017
Published in: Mathematics of Operations Research, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1311.4728
curvaturelocal searchmatroidssubmodular maximizationmaximum entropy samplingcontinuous greedysupermodular minimizationcolumn-subset selection
Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Approximation algorithms (68W25)
Related Items (45)
Tight Approximation Bounds for Maximum Multi-coverage ⋮ A new greedy strategy for maximizing monotone submodular function under a cardinality constraint ⋮ On maximizing the difference between an approximately submodular function and a linear function subject to a matroid constraint ⋮ A linear-time streaming algorithm for cardinality-constrained maximizing monotone non-submodular set functions ⋮ A multi-pass streaming algorithm for regularized submodular maximization ⋮ Bi-criteria adaptive algorithms for minimizing supermodular functions with cardinality constraint ⋮ Maximizing a non-decreasing non-submodular function subject to various types of constraints ⋮ Maximizing a monotone non-submodular function under a knapsack constraint ⋮ Unnamed Item ⋮ A mobile multi-agent sensing problem with submodular functions under a partition matroid ⋮ Performance guarantees of forward and reverse greedy algorithms for minimizing nonsupermodular nonsubmodular functions on a matroid ⋮ FPT approximation schemes for maximizing submodular functions ⋮ Beyond submodularity: a unified framework of randomized set selection with group fairness constraints ⋮ Algorithms for maximizing monotone submodular function minus modular function under noise ⋮ Analyzing Residual Random Greedy for monotone submodular maximization ⋮ An Improved Analysis of Local Search for Max-Sum Diversification ⋮ On streaming algorithms for maximizing a supermodular function plus a MDR-submodular function on the integer lattice ⋮ Improved bounds for the greedy strategy in optimization problems with curvature ⋮ On maximizing sums of non-monotone submodular and linear functions ⋮ Unified Greedy Approximability beyond Submodular Maximization ⋮ Streaming algorithms for maximizing the difference of submodular functions and the sum of submodular and supermodular functions ⋮ Unified greedy approximability beyond submodular maximization ⋮ Bicriteria algorithms for maximizing the difference between submodular function and linear function under noise ⋮ Unnamed Item ⋮ Approximation algorithm of maximizing non-monotone non-submodular functions under knapsack constraint ⋮ Greedy guarantees for non-submodular function maximization under independent system constraint with applications ⋮ Bicriteria algorithms to balance coverage and cost in team formation under online model ⋮ Stochastic Conditional Gradient++: (Non)Convex Minimization and Continuous Submodular Maximization ⋮ Deterministic approximation algorithm for submodular maximization subject to a matroid constraint ⋮ Unnamed Item ⋮ Evaluation of Combinatorial Optimisation Algorithms for c-Optimal Experimental Designs with Correlated Observations ⋮ Unnamed Item ⋮ Performance bounds with curvature for batched greedy optimization ⋮ Online bicriteria algorithms to balance coverage and cost in team formation ⋮ Sequence submodular maximization meets streaming ⋮ Fast algorithms for maximizing monotone nonsubmodular functions ⋮ Improved algorithms for non-submodular function maximization problem ⋮ Maximizing DR-submodular+supermodular functions on the integer lattice subject to a cardinality constraint ⋮ Guess free maximization of submodular and linear sums ⋮ Maximizing a Monotone Submodular Function with a Bounded Curvature under a Knapsack Constraint ⋮ Maximization problems of balancing submodular relevance and supermodular diversity ⋮ Bicriteria streaming algorithms to balance gain and cost with cardinality constraint ⋮ Fast algorithms for supermodular and non-supermodular minimization via bi-criteria strategy ⋮ An adaptive algorithm for maximization of non-submodular function with a matroid constraint ⋮ Tight approximation bounds for maximum multi-coverage
This page was built for publication: Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature
