Back to Search
Start Over
AN ADAPTIVE ALGORITHM FOR MAXIMIZATION OF NON-SUBMODULAR FUNCTION WITH A MATROID CONSTRAINT.
- Source :
- Journal of Industrial & Management Optimization; Mar2023, Vol. 19 Issue 3, p2050-2070, 21p
- Publication Year :
- 2023
-
Abstract
- In the paper, we design an adaptive algorithm for non-submodular set function maximization over a single matroid constraint. We measure the deviation of the set function from fully submodular with the help of the generic submodularity ratio γ. The adaptivity quantifies the information theoretic complexity of oracle optimization for parallel computations. We propose a new approximation algorithm based on the continuous greedy approach and prove that the algorithm could obtain a fractional solution with approximation ratio (1 -- ... -- O(ϵ)) in O(log n log(k/γϵ)/ϵ<superscript>-2</superscript> log n log(1/γ)--ϵ<superscript>-1</superscript>log(1--ϵ) adaptive rounds. We then use the contention resolution schemes to convert the fractional solution to a discrete one with γ(1 -- e<superscript>-1</superscript>)(1 -- ... -- O(ϵ))-approximation. [ABSTRACT FROM AUTHOR]
- Subjects :
- APPROXIMATION algorithms
SET functions
ALGORITHMS
Subjects
Details
- Language :
- English
- ISSN :
- 15475816
- Volume :
- 19
- Issue :
- 3
- Database :
- Complementary Index
- Journal :
- Journal of Industrial & Management Optimization
- Publication Type :
- Academic Journal
- Accession number :
- 160954416
- Full Text :
- https://doi.org/10.3934/jimo.2022031