An adaptive algorithm for maximization of non-submodular function with a matroid constraint
From MaRDI portal
Publication:2097487
DOI10.3934/JIMO.2022031OpenAlexW4226209249MaRDI QIDQ2097487FDOQ2097487
Authors: Yanyan Li 
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
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
- Best Algorithms for Approximating the Maximum of a Submodular Set Function
- Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature
- Monotone submodular maximization over a matroid via non-oblivious local search
- Combinatorial auctions with decreasing marginal utilities
- Maximizing a monotone submodular function subject to a matroid constraint
- An analysis of approximations for maximizing submodular set functions—I
- Fast algorithms for maximizing submodular functions
- Submodular function maximization via the multilinear relaxation and contention resolution schemes
- Parallel Merge Sort
- Near-optimal sensor placements in Gaussian processes: theory, efficient algorithms and empirical studies
- Communication complexity
- Title not available (Why is that?)
- Maximizing Non-monotone Submodular Functions
- Optimal approximation for the submodular welfare problem in the value oracle model
- Title not available (Why is that?)
- Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
- On the use of adjoint-based sensitivity estimates to control local mesh refinement
- The complexity of parallel search
- A Unified Continuous Greedy Algorithm for Submodular Maximization
- An adaptivity hierarchy theorem for property testing
- An efficient algorithm for image segmentation, Markov random fields and related problems
- The power of local search: maximum coverage over a matroid
- Deterministic (½ + ε)-Approximation for Submodular Maximization over a Matroid
- On the Power of Adaptivity in Sparse Recovery
- On multiplicative weight updates for concave and submodular function maximization
- Maximize a monotone function with a generic submodularity ratio
- Parallel algorithms for select and partition with noisy comparisons
- Parametric monotone function maximization with matroid constraints
- An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation
- Locally Adaptive Optimization: Adaptive Seeding for Monotone Submodular Functions
- The adaptive complexity of maximizing a submodular function
- Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time
- Submodular function maximization in parallel via the multilinear relaxation
- Approximation guarantees for deterministic maximization of submodular function with a matroid constraint
- Submodular maximization with nearly optimal approximation, adaptivity and query complexity
- Settling the query complexity of non-adaptive junta testing
- An optimal approximation for submodular maximization under a matroid constraint in the adaptive complexity model
Cited In (7)
- Approximation guarantees for parallelized maximization of monotone non-submodular function with a cardinality constraint
- Approximation guarantees for parallelized maximization of monotone non-submodular function with a cardinality constraint
- Bi-criteria adaptive algorithms for minimizing supermodular functions with cardinality constraint
- 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
- Parallelized maximization of nonsubmodular function subject to a cardinality constraint
- Beyond pointwise submodularity: non-monotone adaptive submodular maximization in linear time
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)
