An adaptive algorithm for maximization of non-submodular function with a matroid constraint
From MaRDI portal
Publication:2097487
Recommendations
- An optimal approximation for submodular maximization under a matroid constraint in the adaptive complexity model
- An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model
- Maximizing approximately non-\(k\)-submodular monotone set function with matroid constraint
- Maximization of \(k\)-submodular function with a matroid constraint
- Maximizing nonmonotone submodular functions under matroid or knapsack constraints
- Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)
- Non-submodular maximization with matroid and knapsack constraints
- Maximization of constrained non-submodular functions
- Maximizing a monotone submodular function subject to a matroid constraint
- Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint
Cites work
- scientific article; zbMATH DE number 1953186 (Why is no real title available?)
- scientific article; zbMATH DE number 6292744 (Why is no real title available?)
- A Unified Continuous Greedy Algorithm for Submodular Maximization
- An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation
- An adaptivity hierarchy theorem for property testing
- An analysis of approximations for maximizing submodular set functions—I
- An efficient algorithm for image segmentation, Markov random fields and related problems
- An optimal approximation for submodular maximization under a matroid constraint in the adaptive complexity model
- Approximation guarantees for deterministic maximization of submodular function with a matroid constraint
- Best Algorithms for Approximating the Maximum of a Submodular Set Function
- Combinatorial auctions with decreasing marginal utilities
- Communication complexity
- Deterministic (½ + ε)-Approximation for Submodular Maximization over a Matroid
- Fast algorithms for maximizing submodular functions
- Locally Adaptive Optimization: Adaptive Seeding for Monotone Submodular Functions
- Maximize a monotone function with a generic submodularity ratio
- Maximizing Non-monotone Submodular Functions
- Maximizing a monotone submodular function subject to a matroid constraint
- Monotone submodular maximization over a matroid via non-oblivious local search
- Near-optimal sensor placements in Gaussian processes: theory, efficient algorithms and empirical studies
- On multiplicative weight updates for concave and submodular function maximization
- On the Power of Adaptivity in Sparse Recovery
- On the use of adjoint-based sensitivity estimates to control local mesh refinement
- Optimal approximation for the submodular welfare problem in the value oracle model
- Parallel Merge Sort
- Parallel algorithms for select and partition with noisy comparisons
- Parametric monotone function maximization with matroid constraints
- Settling the query complexity of non-adaptive junta testing
- Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time
- Submodular function maximization in parallel via the multilinear relaxation
- Submodular function maximization via the multilinear relaxation and contention resolution schemes
- Submodular maximization with nearly optimal approximation, adaptivity and query complexity
- Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
- The adaptive complexity of maximizing a submodular function
- The complexity of parallel search
- The power of local search: maximum coverage over a matroid
Cited in
(7)- Maximizing stochastic set function under a matroid constraint from decomposition
- An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model
- Approximation guarantees for parallelized maximization of monotone non-submodular function with a cardinality constraint
- Beyond pointwise submodularity: non-monotone adaptive submodular maximization in linear time
- Bi-criteria adaptive algorithms for minimizing supermodular functions with cardinality constraint
- Approximation guarantees for parallelized maximization of monotone non-submodular function with a cardinality constraint
- Parallelized maximization of nonsubmodular function subject to a cardinality constraint
This page was built for publication: An adaptive algorithm for maximization of non-submodular function with a matroid constraint
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2097487)
