Maximize a monotone function with a generic submodularity ratio
From MaRDI portal
Publication:2220848
DOI10.1016/j.tcs.2020.05.018zbMath1477.68537OpenAlexW3033884363MaRDI QIDQ2220848
Qizhi Fang, Tao Sun, Suning Gong, Xiaoyu Shao, Qingqin Nong, Ding-Zhu Du
Publication date: 25 January 2021
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2020.05.018
Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)
Related Items (9)
Maximizing a non-decreasing non-submodular function subject to various types of constraints ⋮ Two-stage non-submodular maximization ⋮ Two-stage non-submodular maximization ⋮ Streaming algorithms for maximizing the difference of submodular functions and the sum of submodular and supermodular functions ⋮ Fast algorithms for maximizing monotone nonsubmodular functions ⋮ Fast algorithms for maximizing monotone nonsubmodular functions ⋮ Approximation guarantees for parallelized maximization of monotone non-submodular function with a cardinality constraint ⋮ An adaptive algorithm for maximization of non-submodular function with a matroid constraint ⋮ Improved algorithms for non-submodular function maximization problem
Cites Work
- A framework of discrete DC programming by discrete convex analysis
- Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
- A note on maximizing a submodular set function subject to a knapsack constraint
- The budgeted maximum coverage problem
- About strongly polynomial time algorithms for quadratic optimization over submodular constraints
- A threshold of ln n for approximating set cover
- Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location Problems
- An analysis of approximations for maximizing submodular set functions—I
- Best Algorithms for Approximating the Maximum of a Submodular Set Function
- Learning submodular functions
- Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)
- An efficient algorithm for image segmentation, Markov random fields and related problems
- Submodular Maximization over Multiple Matroids via Generalized Exchange Properties
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Maximize a monotone function with a generic submodularity ratio