scientific article; zbMATH DE number 6783454

zbMath1377.90073arXiv1007.1632MaRDI QIDQ5365102

Shayan Oveis Gharan, Jan Vondrák

Publication date: 29 September 2017

Full work available at URL: https://arxiv.org/abs/1007.1632

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items

A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization ⋮ Maximizing Symmetric Submodular Functions ⋮ Measured continuous greedy with differential privacy ⋮ Robust Monotone Submodular Function Maximization ⋮ Submodular Functions: Learnability, Structure, and Optimization ⋮ Unnamed Item ⋮ The Power of Subsampling in Submodular Maximization ⋮ A 1/2-approximation algorithm for maximizing a non-monotone weak-submodular function on a bounded integer lattice ⋮ Bounds on Double-Sided Myopic Algorithms for Unconstrained Non-monotoneSubmodular Maximization ⋮ Optimization with demand oracles ⋮ Maximizing non-monotone submodular set functions subject to different constraints: combined algorithms ⋮ Constrained Submodular Maximization via a Nonsymmetric Technique ⋮ A single factor approximation ratio algorithm for DR-submodular maximization on integer lattice beyond non-negativity and monotonicity ⋮ On maximizing sums of non-monotone submodular and linear functions ⋮ Improved deterministic algorithms for non-monotone submodular maximization ⋮ Improved deterministic algorithms for non-monotone submodular maximization ⋮ A binary search double greedy algorithm for non-monotone DR-submodular maximization ⋮ Deterministic \(\boldsymbol{(\unicode{x00BD}+\varepsilon)}\) -Approximation for Submodular Maximization over a Matroid ⋮ A fast algorithm for maximizing a non-monotone DR-submodular integer lattice function ⋮ Profit maximization in social networks and non-monotone DR-submodular maximization ⋮ A Survey on Double Greedy Algorithms for Maximizing Non-monotone Submodular Functions ⋮ Stochastic Conditional Gradient++: (Non)Convex Minimization and Continuous Submodular Maximization ⋮ The Submodular Secretary Problem Goes Linear ⋮ Explaining anomalies in groups with characterizing subspace rules ⋮ Nonmonotone Submodular Maximization via a Structural Continuous Greedy Algorithm ⋮ Weakly Submodular Function Maximization Using Local Submodularity Ratio. ⋮ Non-monotone submodular function maximization under \(k\)-system constraint ⋮ Monotone submodular maximization over the bounded integer lattice with cardinality constraints ⋮ Limitations of randomized mechanisms for combinatorial auctions ⋮ Sequence submodular maximization meets streaming ⋮ Robust monotone submodular function maximization ⋮ A fast double greedy algorithm for non-monotone DR-submodular function maximization ⋮ Online Submodular Maximization with Preemption ⋮ Improved Competitive Ratios for Submodular Secretary Problems (Extended Abstract) ⋮ Private non-monotone submodular maximization ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Two approximation algorithms for maximizing nonnegative weakly monotonic set functions ⋮ An optimal monotone contention resolution scheme for bipartite matchings via a polyhedral viewpoint