Maximize a monotone function with a generic submodularity ratio

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

zbMATH Keywords

greedynon-submodularindependent system

Mathematics Subject Classification ID

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