Maximize a monotone function with a generic submodularity ratio
DOI10.1016/J.TCS.2020.05.018zbMATH Open1477.68537OpenAlexW3033884363MaRDI QIDQ2220848FDOQ2220848
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
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
Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)
Cites Work
- A threshold of ln n for approximating set cover
- Best Algorithms for Approximating the Maximum of a Submodular Set Function
- Title not available (Why is that?)
- The budgeted maximum coverage problem
- Title not available (Why is that?)
- An analysis of approximations for maximizing submodular set functions—I
- Submodular maximization over multiple matroids via generalized exchange properties
- About strongly polynomial time algorithms for quadratic optimization over submodular constraints
- Near-optimal sensor placements in Gaussian processes: theory, efficient algorithms and empirical studies
- Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)
- A note on maximizing a submodular set function subject to a knapsack constraint
- Learning submodular functions
- 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
- An efficient algorithm for image segmentation, Markov random fields and related problems
- Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location Problems
Cited In (16)
- Improved algorithms for non-submodular function maximization problem
- An adaptive algorithm for maximization of non-submodular function with a matroid constraint
- 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
- Approximation guarantees for parallelized maximization of monotone non-submodular function with a cardinality constraint
- Maximizing a non-decreasing non-submodular function subject to various types of constraints
- 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
- 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)
