A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization
From MaRDI portal
Publication:3449564
DOI10.1137/130929205zbMath1330.68346OpenAlexW2179494254MaRDI QIDQ3449564
Roy Schwartz, Niv Buchbinder, Moran Feldman, Joseph Seffi
Publication date: 4 November 2015
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.361.1263
Related Items (45)
Submodular Maximization Subject to a Knapsack Constraint Under Noise Models ⋮ Fast Distributed Approximation for Max-Cut ⋮ Some Inapproximability Results of MAP Inference and Exponentiated Determinantal Point Processes ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Maximizing \(k\)-submodular functions under budget constraint: applications and streaming algorithms ⋮ A 1/2-approximation algorithm for maximizing a non-monotone weak-submodular function on a bounded integer lattice ⋮ An Experimental Evaluation of Fast Approximation Algorithms for the Maximum Satisfiability Problem ⋮ On additive approximate submodularity ⋮ Improved approximation algorithms for \(k\)-submodular maximization under a knapsack constraint ⋮ Two-stage submodular maximization under knapsack and matroid constraints ⋮ 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 ⋮ Target users' activation probability maximization with different seed set constraints in social networks ⋮ A binary search double greedy algorithm for non-monotone DR-submodular maximization ⋮ Deterministic \(\boldsymbol{(\unicode{x00BD}+\varepsilon)}\) -Approximation for Submodular Maximization over a Matroid ⋮ An exact solution approach for the mobile multi‐agent sensing problem ⋮ Unnamed Item ⋮ A fast algorithm for maximizing a non-monotone DR-submodular integer lattice function ⋮ Local search algorithms for the maximum carpool matching problem ⋮ Profit maximization in social networks and non-monotone DR-submodular maximization ⋮ A Survey on Double Greedy Algorithms for Maximizing Non-monotone Submodular Functions ⋮ On extensions of the deterministic online model for bipartite matching and max-sat ⋮ Simple approximation algorithms for balanced MAX~2SAT ⋮ On maximizing a monotone \(k\)-submodular function subject to a matroid constraint ⋮ Equilibria of Greedy Combinatorial Auctions ⋮ Coreness of cooperative games with truncated submodular profit functions ⋮ Unnamed Item ⋮ 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 ⋮ Approximation guarantees for parallelized maximization of monotone non-submodular function with a cardinality constraint ⋮ Unnamed Item ⋮ A fast double greedy algorithm for non-monotone DR-submodular function maximization ⋮ Online Submodular Maximization with Preemption ⋮ Greedy differencing edge-contraction heuristic for the max-cut problem ⋮ Maximizing submodular or monotone approximately submodular functions by multi-objective evolutionary algorithms ⋮ The submodularity of two-stage stochastic maximum-weight independent set problems ⋮ Improved Randomized Algorithm for k-Submodular Function Maximization ⋮ k-Submodular maximization with two kinds of constraints ⋮ Unnamed Item ⋮ Two approximation algorithms for maximizing nonnegative weakly monotonic set functions ⋮ Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds ⋮ Tight Approximation for Unconstrained XOS Maximization
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Graph cuts with interacting edge weights: examples, approximations, and algorithms
- Maximizing a class of submodular utility functions
- The ellipsoid method and its consequences in combinatorial optimization
- Maximizing a submodular function by integer programming: Polyhedral results for the quadratic case
- An 0. 828-approximation algorithm for the uncapacitated facility location problem
- Approximating the least core value and least core of cooperative games with supermodular costs
- A multilevel search algorithm for the maximization of submodular functions applied to the quadratic cost partition problem
- Bounds on Double-Sided Myopic Algorithms for Unconstrained Non-monotoneSubmodular Maximization
- Nonmonotone Submodular Maximization via a Structural Continuous Greedy Algorithm
- Maximizing Nonmonotone Submodular Functions under Matroid or Knapsack Constraints
- Maximizing Non-monotone Submodular Functions
- Submodular Approximation: Sampling-based Algorithms and Lower Bounds
- Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
- Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Gadgets, Approximation, and Linear Programming
- The Data-Correcting Algorithm for the Minimization of Supermodular Functions
- Reducibility among Combinatorial Problems
- Submodular Function Minimization under Covering Constraints
- Symmetry and Approximability of Submodular Maximization Problems
- Submodular Maximization with Cardinality Constraints
- From query complexity to computational complexity
- Submodular function maximization via the multilinear relaxation and contention resolution schemes
- Some optimal inapproximability results
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- A Unified Continuous Greedy Algorithm for Submodular Maximization
- Submodular Maximization over Multiple Matroids via Generalized Exchange Properties
This page was built for publication: A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization
