Bounds on Double-Sided Myopic Algorithms for Unconstrained Non-monotoneSubmodular Maximization
From MaRDI portal
Publication:2942658
DOI10.1007/978-3-319-13075-0_42zbMath1433.68620arXiv1312.2173OpenAlexW1825657983MaRDI QIDQ2942658
Publication date: 11 September 2015
Published in: Algorithms and Computation (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1312.2173
Combinatorial optimization (90C27) Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)
Related Items (9)
A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization ⋮ Maximizing Symmetric Submodular Functions ⋮ Bounds on Double-Sided Myopic Algorithms for Unconstrained Non-monotoneSubmodular Maximization ⋮ On maximizing sums of non-monotone submodular and linear functions ⋮ Online algorithms for BP functions maximization ⋮ On extensions of the deterministic online model for bipartite matching and max-sat ⋮ Greedy matching: guarantees and limitations ⋮ Online BP functions maximization ⋮ Online Submodular Maximization with Preemption
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Online maximum directed cut
- A note on maximizing a submodular set function subject to a knapsack constraint
- Oblivious algorithms for the maximum directed cut problem
- Bounds on Double-Sided Myopic Algorithms for Unconstrained Non-monotoneSubmodular Maximization
- Nonmonotone Submodular Maximization via a Structural Continuous Greedy Algorithm
- Bounds on Greedy Algorithms for MAX SAT
- Maximizing Non-monotone Submodular Functions
- A threshold of ln n for approximating set cover
- Maximum directed cuts in acyclic digraphs
- Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
- An analysis of approximations for maximizing submodular set functions—I
- Best Algorithms for Approximating the Maximum of a Submodular Set Function
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Non-monotone submodular maximization under matroid and knapsack constraints
- Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)
This page was built for publication: Bounds on Double-Sided Myopic Algorithms for Unconstrained Non-monotoneSubmodular Maximization