Bounds on Double-Sided Myopic Algorithms for Unconstrained Non-monotoneSubmodular Maximization

DOI10.1007/978-3-319-13075-0_42zbMath1433.68620arXiv1312.2173OpenAlexW1825657983MaRDI QIDQ2942658

Allan Borodin, Norman Huang

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

Mathematics Subject Classification ID

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