Maximize a monotone function with a generic submodularity ratio

DOI10.1016/J.TCS.2020.05.018MaRDI QIDQ2220848zbMATH OpenOpenAlexFDO

Authors Suning Gong, Qingqin Nong, Tao Sun, Qizhi Fang, Du Ding-Zhu, Xiaoyu Shao

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)

Recommendations

• Fast algorithms for maximizing monotone nonsubmodular functions
• Fast algorithms for maximizing monotone nonsubmodular functions
• Greedy guarantees for non-submodular function maximization under independent system constraint with applications
• Approximation for maximizing monotone non-decreasing set functions with a greedy method
• Non-submodular maximization with matroid and knapsack constraints

Cites work

• scientific article; zbMATH DE number 3544074 (Why is no real title available?)
• scientific article; zbMATH DE number 3635849 (Why is no real title available?)
• A framework of discrete DC programming by discrete convex analysis
• A note on maximizing a submodular set function subject to a knapsack constraint
• A threshold of ln n for approximating set cover
• About strongly polynomial time algorithms for quadratic optimization over submodular constraints
• An analysis of approximations for maximizing submodular set functions—I
• An efficient algorithm for image segmentation, Markov random fields and related problems
• Best Algorithms for Approximating the Maximum of a Submodular Set Function
• Learning submodular functions
• Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location Problems
• Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)
• Near-optimal sensor placements in Gaussian processes: theory, efficient algorithms and empirical studies
• Submodular maximization over multiple matroids via generalized exchange properties
• Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
• The budgeted maximum coverage problem

Cited in

(16)

• Two-stage non-submodular maximization
• An adaptive algorithm for maximization of non-submodular function with a matroid constraint
• Improved algorithms for non-submodular function maximization problem
• Fast deterministic algorithms for non-submodular maximization with strong performance guarantees
• Greedy is good: constrained non-submodular function maximization via weak submodularity
• Minimizing ratio of monotone non-submodular functions
• Maximizing a non-decreasing non-submodular function subject to various types of constraints
• Approximation guarantees for parallelized maximization of monotone non-submodular function with a cardinality constraint
• Streaming algorithms for maximizing the difference of submodular functions and the sum of submodular and supermodular functions
• Unified greedy approximability beyond submodular maximization
• Maximize a monotone function with a generic submodularity ratio
• Maximizing Non-monotone Submodular Functions
• Weak submodularity implies localizability: local search for constrained non-submodular function maximization
• Fast algorithms for maximizing monotone nonsubmodular functions
• Fast algorithms for maximizing monotone nonsubmodular functions
• Two-stage non-submodular maximization

This page was built for publication: Maximize a monotone function with a generic submodularity ratio

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2220848)