An adaptive algorithm for maximization of non-submodular function with a matroid constraint
From MaRDI portal
Publication:2097487
DOI10.3934/jimo.2022031OpenAlexW4226209249MaRDI QIDQ2097487
Publication date: 14 November 2022
Published in: Journal of Industrial and Management Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.3934/jimo.2022031
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
- Communication complexity
- The complexity of parallel search
- An adaptivity hierarchy theorem for property testing
- Parametric monotone function maximization with matroid constraints
- Approximation guarantees for deterministic maximization of submodular function with a matroid constraint
- Maximize a monotone function with a generic submodularity ratio
- Combinatorial auctions with decreasing marginal utilities
- On Multiplicative Weight Updates for Concave and Submodular Function Maximization
- Maximizing Non-monotone Submodular Functions
- Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
- Parallel Merge Sort
- An analysis of approximations for maximizing submodular set functions—I
- Best Algorithms for Approximating the Maximum of a Submodular Set Function
- Locally Adaptive Optimization: Adaptive Seeding for Monotone Submodular Functions
- Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature
- Settling the Query Complexity of Non-adaptive Junta Testing
- Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes
- An optimal approximation for submodular maximization under a matroid constraint in the adaptive complexity model
- The adaptive complexity of maximizing a submodular function
- Deterministic (½ + ε)-Approximation for Submodular Maximization over a Matroid
- 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
- Submodular Function Maximization in Parallel via the Multilinear Relaxation
- On the Use of Adjoint-based Sensitivity Estimates to Control Local Mesh Refinement
- Parallel algorithms for select and partition with noisy comparisons
- Fast algorithms for maximizing submodular functions
- An efficient algorithm for image segmentation, Markov random fields and related problems
- Monotone Submodular Maximization over a Matroid via Non-Oblivious Local Search
- On the Power of Adaptivity in Sparse Recovery
- A Unified Continuous Greedy Algorithm for Submodular Maximization
This page was built for publication: An adaptive algorithm for maximization of non-submodular function with a matroid constraint