Fast algorithms for maximizing monotone nonsubmodular functions
From MaRDI portal
Publication:5918746
DOI10.1007/s10878-021-00717-1zbMath1495.90158OpenAlexW4252671011MaRDI QIDQ5918746
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
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