Fast algorithms for maximizing monotone nonsubmodular functions

DOI10.1007/s10878-021-00717-1zbMath1495.90158OpenAlexW4252671011MaRDI QIDQ5918746

Bin Liu, Miaomiao Hu

Publication date: 18 July 2022

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-021-00717-1

zbMATH Keywords

approximation algorithmmatroid constraintcardinality constraintnonsubmodular function

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• Solving the degree-concentrated fault-tolerant spanning subgraph problem by DC programming
• Pipage rounding: a new method of constructing algorithms with proven performance guarantee
• Restricted strong convexity implies weak submodularity
• Parametric monotone function maximization with matroid constraints
• Non-submodular streaming maximization with minimum memory and low adaptive complexity
• Streaming algorithm for maximizing a monotone non-submodular function under \(d\)-knapsack constraint
• Maximize a monotone function with a generic submodularity ratio
• Greedy algorithm for maximization of non-submodular functions subject to knapsack constraint
• Non-submodular maximization on massive data streams
• Set function optimization
• Constrained Monotone Function Maximization and the Supermodular Degree
• Welfare maximization and the supermodular degree
• Maximizing Non-monotone Submodular Functions
• A threshold of ln n for approximating set cover
• An analysis of approximations for maximizing submodular set functions—I
• Best Algorithms for Approximating the Maximum of a Submodular Set Function
• Deterministic Algorithms for Submodular Maximization Problems
• Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature
• Constrained Submodular Maximization via a Nonsymmetric Technique
• The one-way communication complexity of submodular maximization with applications to streaming and robustness
• The adaptive complexity of maximizing a submodular function
• Submodular Maximization with Nearly Optimal Approximation, Adaptivity and Query Complexity
• Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time
• An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation
• Fast algorithms for maximizing submodular functions
• Submodular function maximization via the multilinear relaxation and contention resolution schemes
• Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)

This page was built for publication: Fast algorithms for maximizing monotone nonsubmodular functions