An adaptive algorithm for maximization of non-submodular function with a matroid constraint
type: Item
instance of: scholarly article
title: An adaptive algorithm for maximization of non-submodular function with a matroid constraint
author: Yanyan Li
published in: Journal of Industrial and Management Optimization
publication date: 2022-11-14T00:00:00Z
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 7616043
zbMATH Keywords: approximation algorithm
zbMATH Keywords: non-submodular
zbMATH Keywords: generic submodularity ratio
zbMATH Keywords: matroid constraints
zbMATH Keywords: adaptivity
MaRDI profile type: Publication
full work available at URL: jimo.2022031
OpenAlex ID: W4226209249
cites work: Fast algorithms for maximizing submodular functions
cites work: Locally Adaptive Optimization: Adaptive Seeding for Monotone Submodular Functions
cites work: An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation
cites work: An optimal approximation for submodular maximization under a matroid constraint in the adaptive complexity model
cites work: The adaptive complexity of maximizing a submodular function
cites work: Parallel algorithms for select and partition with noisy comparisons
cites work: Deterministic (½ + ε)-Approximation for Submodular Maximization over a Matroid
cites work: Q5414625
cites work: Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
cites work: An adaptivity hierarchy theorem for property testing
cites work: On Multiplicative Weight Updates for Concave and Submodular Function Maximization
cites work: Submodular Function Maximization in Parallel via the Multilinear Relaxation
cites work: Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes
cites work: Settling the Query Complexity of Non-adaptive Junta Testing
cites work: Parallel Merge Sort
cites work: Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
cites work: Q4414632
cites work: Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time
cites work: Submodular Maximization with Nearly Optimal Approximation, Adaptivity and Query Complexity
cites work: Maximizing Non-monotone Submodular Functions
cites work: A Unified Continuous Greedy Algorithm for Submodular Maximization
cites work: Monotone Submodular Maximization over a Matroid via Non-Oblivious Local Search
cites work: The power of local search: maximum coverage over a matroid
cites work: On the Use of Adjoint-based Sensitivity Estimates to Control Local Mesh Refinement
cites work: Parametric monotone function maximization with matroid constraints
cites work: An efficient algorithm for image segmentation, Markov random fields and related problems
cites work: On the Power of Adaptivity in Sparse Recovery
cites work: The complexity of parallel search
cites work: Q3096108
cites work: Combinatorial auctions with decreasing marginal utilities
cites work: Best Algorithms for Approximating the Maximum of a Submodular Set Function
cites work: An analysis of approximations for maximizing submodular set functions—I
cites work: Maximize a monotone function with a generic submodularity ratio
cites work: Communication complexity
cites work: Approximation guarantees for deterministic maximization of submodular function with a matroid constraint
cites work: Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature
cites work: Q3549686
DOI: 10.3934/JIMO.2022031
Recommended article: An optimal approximation for submodular maximization under a matroid constraint in the adaptive complexity model
Recommended article: An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model
Recommended article: Maximizing approximately non-\(k\)-submodular monotone set function with matroid constraint
Recommended article: Maximization of \(k\)-submodular function with a matroid constraint
Recommended article: Maximizing Nonmonotone Submodular Functions under Matroid or Knapsack Constraints
Recommended article: Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)
Recommended article: Non-Submodular Maximization with Matroid and Knapsack Constraints
Recommended article: Maximization of constrained non-submodular functions
Recommended article: Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
Recommended article: Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint
description: scientific article; zbMATH DE number 7616043