• Previous Article
    A novel separate chance-constrained programming model to design a sustainable medical ventilator supply chain network during the Covid-19 pandemic
  • JIMO Home
  • This Issue
  • Next Article
    $ \alpha $-robust portfolio optimization problem under the distribution uncertainty
doi: 10.3934/jimo.2022031
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

An adaptive algorithm for maximization of non-submodular function with a matroid constraint

1. 

Beijing Institute for Scientific and Engineering Computing, Beijing University of Technology, Beijing 100124, China

2. 

School of Computer Science and Technology, Shandong Jianzhu University, Jinan 250101, China

3. 

School of Mathematics and Statistics, Shandong Normal University, Jinan 250014, China

*Corresponding author: Yang Zhou

A preliminary version of this paper appeared in Proceedings of the 9th International Conference on Computational Data and Social Networks, pp. 3-13, 2020

Received  September 2021 Revised  December 2021 Early access March 2022

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 $ \gamma $. 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-e^{-{\gamma}^2}-\mathcal{O}(\epsilon)) $ in $ \mathcal{O}\left(\frac{\log n\log(k/\gamma\epsilon)} {\epsilon^{-2} \log n\log(1/\gamma)-\epsilon^{-1}\log(1-\epsilon)}\right) $ adaptive rounds. We then use the contention resolution schemes to convert the fractional solution to a discrete one with $ \gamma(1-e^{-1})(1-e^{-{\gamma}^2}-\mathcal{O}(\epsilon)) $-approximation.

Citation: Xin Sun, Dachuan Xu, Dongmei Zhang, Yang Zhou. An adaptive algorithm for maximization of non-submodular function with a matroid constraint. Journal of Industrial and Management Optimization, doi: 10.3934/jimo.2022031
References:
[1]

Agarwal A, Agarwal S, Assadi S, Khanna S. Learning with limited rounds of adaptivity: Coin tossing, multi-armed bandits, and ranking from pairwise comparisons. In Proceedings of the 30th Annual Conference on Leraning Theory, pp. 39-75 (2017)

[2]

Alon N, Spencer JH. The Probabilistic Method. John Wiley & Sons, Volume 3, pp. 307-314 (2004)

[3]

Altschuler J, Bhaskara A, Fu G, Mirrokni V, Rostamizadeh A, Zadimoghaddam M. Greedy column subset selection: New bounds and distributed algorithms. In Proceedings of the 33rd International Conference on Machine Learning, pp. 2539-2548 (2016)

[4]

Badanidiyuru A, Vondrák J. Fast algorithms for maximizing submodular functions. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1497-1514 (2014) doi: 10.1137/1.9781611973402.110.

[5]

Badanidiyuru A, Papadimitriou C, Rubinstein A, Seeman L, Singer Y. Locally adaptive optimization: Adaptive seeding for monotone submodular functions. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 414-429 (2016) doi: 10.1137/1.9781611974331.ch31.

[6]

Balkanski E, Rubinstein A, Singer Y. An exponential speedup in parallel running time for submodular maximization without loss in approximation. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 283-302 (2019) doi: 10.1137/1.9781611975482.19.

[7]

Balkanski E, Rubinstein A, Singer Y. An optimal approximation for submodular maximization under a matroid constraint in the adaptive complexity model. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pp. 66-77 (2019) doi: 10.1145/3313276.3316304.

[8]

Balkanski E, Singer Y. The adaptive complexity of maximizing a submodular function. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pp. 1138-1151 (2018) doi: 10.1145/3188745.3188752.

[9]

Balkanski E, Singer Y. Approximation guarantees for adaptive sampling. In Proceedings of the 35th International Conference on Machine Learning, pp. 393-402 (2018)

[10]

Bian AA, Buhmann JM, Krause A, Tschiatschek S. Guarantees for greedy maximization of non-submodular functions with applications. In Proceedings of the 34th International Conference on Machine Learning, pp. 498-507 (2017)

[11]

GR BowmanVA Voelz and VS Pande, Taming the complexity of protein folding, Current opinion in structural biology, 21 (2011), 4-11. 

[12]

Braverman M, Mao J, Weinberg SM. Parallel algorithms for select and partition with noisy comparisons. In Proceedings of the 48th Annual ACM Symposium on Theory of Computing, pp. 851-862 (2016) doi: 10.1145/2897518.2897642.

[13]

Buchbinder N, Feldman M, Garg M. Deterministic (1/2+$\varepsilon$)-approximation for submodular maximization over a matroid. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 241-254 (2019) doi: 10.1137/1.9781611975482.16.

[14]

H BuhrmanD García-SorianoA Matsliah and R de Wolf, The non-adaptive query complexity of testing k-parities, Chicago Journal of Theoretical Computer Science, 2013 (2013), 1-11. 

[15]

G CălinescuC ChekuriM Pál and J Vondrák, Maximizing a monotone submodular function subject to a matroid constraint, SIAM Journal on Computing, 40 (2011), 1740-1766. 

[16]

C Canonne and T Gur, An adaptivity hierarchy theorem for property testing, Computational Complexity, 27 (2018), 671-716. 

[17]

Chekuri C, Jayram T S, Vondrák J. On multiplicative weight updates for concave and submodular function maximization. In Proceedings of the 6th Innovations in Theoretical Computer Science, pp. 201-210 (2015) doi: 10.1145/2688073.2688086.

[18]

Chekuri C, Quanrud K. Submodular function maximization in parallel via the multilinear relaxation. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 303-322 (2019) doi: 10.1137/1.9781611975482.20.

[19]

Chekuri C, Vondrák J, Zenklusen R. Dependent randomized rounding for matroid polytopes and applications. In Proceedings of the 51st Annual Symposium on Foundations of Computer Science, pp. 575-584 (2010)

[20]

C ChekuriJ Vondrák and R Zenklusen, Submodular function maximization via the multilinear relaxation and contention resolution schemes, SIAM Journal on Computing, 43 (2014), 1831-1879. 

[21]

X ChenRA ServedioLY TanE Waingarten and J Xie, Settling the query complexity of non-adaptive junta testing, Journal of the ACM, 65 (2018), 1-18. 

[22]

R Cole, Parallel merge sort, SIAM Journal on Computing, 17 (1988), 770-785. 

[23]

M Conforti and G Cornuéjols, Submodular set functions, matroids and the greedy algorithm: tight worst-case bounds and some generalizations of the Rado-Edmonds theorem, Journal of Discrete Applied Mathematics, 7 (1984), 251-274. 

[24]

Das A, Kempe D. Submodular meets Spectral: Greedy Algorithms for Subset Selection, Sparse Approximation and Dictionary Selection. In Proceedings of the 28th International Conference on Machine Learning, pp. 1057-1064 (2011)

[25]

NR DevanurZ HuangN KorulaVS Mirrokni and Q Yan, Whole-page optimization and submodular welfare maximization with online bidders, Journal of ACM Transactions on Economics and Computation, 4 (2016), 1-20. 

[26]

Edmonds J. Submodular Functions, Matroids, and Certain Polyhedra. Combinatorial Optimization, Volume 2570, pp. 11-26 (2003) doi: 10.1007/3-540-36478-1_2.

[27]

Ene A, Nguyen HL. Submodular maximization with nearly-optimal approximation and adaptivity in nearly-linear time. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 274-282 (2019) doi: 10.1137/1.9781611975482.18.

[28]

Fahrbach M, Mirrokni V, Zadimoghaddam M. Submodular maximization with optimal approximation, adaptivity and query complexity. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 255-273 (2019) doi: 10.1137/1.9781611975482.17.

[29]

U FeigeV S Mirrokni and J Vondrák, Maximizing non-monotone submodular functions, SIAM Journal on Computing, 40 (2011), 1133-1153. 

[30]

Feldman M, Naor J, Schwartz R. A unified continuous greedy algorithm for submodular maximization. In Proceedings of the 52nd Annual Symposium on Foundations of Computer Science, pp. 570-579 (2011) doi: 10.1109/FOCS.2011.46.

[31]

Y Filmus and J Ward, Monotone submodular maximization over a matroid via non-oblivious local search, SIAM Journal on Computing, 43 (2014), 514-542. 

[32]

Filmus Y, Ward J. The power of local search: Maximum coverage over a matroid. In Proceedings of the 29th Annual Symposium on Theoretical Aspects of Computer Science, 14: 601-612 (2012)

[33]

JD FrazierPK Jimack and RM Kirby, On the use of adjoint-based sensitivity estimates to control local mesh refinement, Communications in Computational Physics, 7 (2010), 631-8. 

[34]

S GongQ NongW Liu and Q Fang, Parametric monotone function maximization with matroid constraints, Journal of Global Optimization, 75 (2019), 833-849. 

[35]

Haupt JD, Baraniuk RG, Castro RM, Nowak RD. Compressive distilled sensing: Sparse recovery using adaptivity in compressive measurements. In Proceedings of the 43rd Asilomar Conference on Signals, Systems and Computers, pp. 1551-1555 (2009)

[36]

Haupt J, Nowak R, Castro R. Adaptive sensing for sparse signal recovery. In Proceedings of the 13th Digital Signal Processing Workshop and 5th IEEE Signal Processing Education Workshop, pp. 702-707 (2009)

[37]

R HerbrichN Lawrence and M Seeger, Fast sparse gaussian process methods: the informative vector machine, Advances in Neural Information Processing System, 15 (2003), 625-632. 

[38]

DS Hochbaum, An efficient algorithm for image segmentation, Markov random fields and related problems, Journal of the ACM, 48 (2001), 686-701. 

[39]

Indyk P, Price E, Woodruff DP. On the power of adaptivity in sparse recovery. In Proceedings of the 52nd Annual Symposium on Foundations of Computer Science, pp. 285-294 (2011) doi: 10.1109/FOCS.2011.83.

[40]

RM KarpE Upfal and A Wigderson, The complexity of parallel search, Journal of Computing System Sciences, 36 (1988), 225-253. 

[41]

Kempe D, Kleinberg JM, Tardos E. Maximizing the spread of influence through a social network. In Proceedings of the 9th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 137-146 (2003)

[42]

Krause A, Guestrin C. Near-optimal nonmyopic value of information in graphical models. In Proceedings of the 21st Conference in Uncertainty in Artificial Intelligence, pp. 324-331 (2005)

[43]

Krause A, Guestrin C. Near-optimal observation selection using submodular functions. In Proceedings of the 32nd AAAI Conference on Artificial Intelligence, pp. 1650-1654 (2007)

[44]

A KrauseA Singh and C Guestrin, Nearoptimal sensor placements in gaussian processes: theory, efficient algorithms and empirical studies, Journal of Machine Learning Research, 9 (2008), 235-284. 

[45]

Kuhnle A, Smith JD, Crawford VG, Thai MT, Fast maximization of Non-submodular, Monotonic Functions on the Integer Lattice. In Proceedings of the 35th International Conference on Machine Learning, pp. 2786-2795 (2018)

[46]

B LehmannD Lehmann and N Nisan, Combinatorial auctions with decreasing marginal utilities, Games and Economic Behavior, 55 (2006), 270-296. 

[47]

Lin H, Bilmes JA. A class of submodular functions for document summarization. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, pp. 510-520 (2011)

[48]

B Lin and M Hu, Fast algorithms for maximizing monotone nonsubmodular functions, Journal of Combinatorial Optimization, (2021). 

[49]

GL Nemhauser and LA Wolsey, Best algorithms for approximating the maximum of a submodular set function, Mathematics of Operations Research, 3 (1978), 177-188. 

[50]

GL NemhauserLA Wolsey and ML Fisher, An analysis of approximations for maximizing submodular set functions–I, Mathematical Programming, 14 (1978), 265-294. 

[51]

Nisan N, Widgerson A. Rounds in communication complexity revisited. In Proceedings of the 23rd Annual ACM Symposium on Theory of computing, pp. 419-429 (1991) doi: 10.1137/0222016.

[52]

Nong Q, Sun T, Gong S, Fang Q, Du D, Shao X. Maximize a monotone function with a generic submodularity ratio. Journal of Theoretical Computer Science https://doi.org/10.1016/j.tcs.2020.05.018 (2020)

[53]

CH Papadimitriou and M Sipser, Communication complexity, Journal of Computer and System Sciences, 28 (1984), 260-269. 

[54]

Rafiey A, Yoshida Y. Fast and Private Submodular and $k$-Submodular Functions Maximization with Matroid Constraints. In Proceedings of the 37th International Conference on Machine Learning, pp. 7887-7897 (2020)

[55]

Singla A, Tschiatschek S, Krause A. Noisy submodular maximization via adaptive sampling with applications to crowdsourced image collection summarization. In Proceedings of the 30th AAAI Conference on Artificial Intelligence, pp. 2037-2043 (2016)

[56]

Streeter MJ, Golovin D. An online algorithm for maximizing submodular functions. In Proceedings of the 22nd International Conference on Advances in Neural Information Processing Systems, pp. 1577-1584 (2008)

[57]

Sun X, Xu D, Guo L, Li M. Approximation Guarantees for Deterministic Maximization of Submodular Function with a Matroid Constraint. In Proceedings of the 16th International Conference on Theory and Applications of Models of Computation (TAMC), pp. 205-214 (2020) doi: 10.1007/978-3-030-59267-7_18.

[58]

M SviridenkoJ Vondrák and J. Ward, Optimal approximation for submodular and supermodular optimization with bounded curvature, Mathematics of Operations Research, 42 (2017), 1197-1218. 

[59]

Vondrák J. Optimal approximation for the submodular welfare problem in the value oracle model. In Proceedings of the 40th Annual ACM symposium on Theory of computing, pp. 67-74 (2008) doi: 10.1145/1374376.1374389.

show all references

References:
[1]

Agarwal A, Agarwal S, Assadi S, Khanna S. Learning with limited rounds of adaptivity: Coin tossing, multi-armed bandits, and ranking from pairwise comparisons. In Proceedings of the 30th Annual Conference on Leraning Theory, pp. 39-75 (2017)

[2]

Alon N, Spencer JH. The Probabilistic Method. John Wiley & Sons, Volume 3, pp. 307-314 (2004)

[3]

Altschuler J, Bhaskara A, Fu G, Mirrokni V, Rostamizadeh A, Zadimoghaddam M. Greedy column subset selection: New bounds and distributed algorithms. In Proceedings of the 33rd International Conference on Machine Learning, pp. 2539-2548 (2016)

[4]

Badanidiyuru A, Vondrák J. Fast algorithms for maximizing submodular functions. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1497-1514 (2014) doi: 10.1137/1.9781611973402.110.

[5]

Badanidiyuru A, Papadimitriou C, Rubinstein A, Seeman L, Singer Y. Locally adaptive optimization: Adaptive seeding for monotone submodular functions. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 414-429 (2016) doi: 10.1137/1.9781611974331.ch31.

[6]

Balkanski E, Rubinstein A, Singer Y. An exponential speedup in parallel running time for submodular maximization without loss in approximation. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 283-302 (2019) doi: 10.1137/1.9781611975482.19.

[7]

Balkanski E, Rubinstein A, Singer Y. An optimal approximation for submodular maximization under a matroid constraint in the adaptive complexity model. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pp. 66-77 (2019) doi: 10.1145/3313276.3316304.

[8]

Balkanski E, Singer Y. The adaptive complexity of maximizing a submodular function. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pp. 1138-1151 (2018) doi: 10.1145/3188745.3188752.

[9]

Balkanski E, Singer Y. Approximation guarantees for adaptive sampling. In Proceedings of the 35th International Conference on Machine Learning, pp. 393-402 (2018)

[10]

Bian AA, Buhmann JM, Krause A, Tschiatschek S. Guarantees for greedy maximization of non-submodular functions with applications. In Proceedings of the 34th International Conference on Machine Learning, pp. 498-507 (2017)

[11]

GR BowmanVA Voelz and VS Pande, Taming the complexity of protein folding, Current opinion in structural biology, 21 (2011), 4-11. 

[12]

Braverman M, Mao J, Weinberg SM. Parallel algorithms for select and partition with noisy comparisons. In Proceedings of the 48th Annual ACM Symposium on Theory of Computing, pp. 851-862 (2016) doi: 10.1145/2897518.2897642.

[13]

Buchbinder N, Feldman M, Garg M. Deterministic (1/2+$\varepsilon$)-approximation for submodular maximization over a matroid. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 241-254 (2019) doi: 10.1137/1.9781611975482.16.

[14]

H BuhrmanD García-SorianoA Matsliah and R de Wolf, The non-adaptive query complexity of testing k-parities, Chicago Journal of Theoretical Computer Science, 2013 (2013), 1-11. 

[15]

G CălinescuC ChekuriM Pál and J Vondrák, Maximizing a monotone submodular function subject to a matroid constraint, SIAM Journal on Computing, 40 (2011), 1740-1766. 

[16]

C Canonne and T Gur, An adaptivity hierarchy theorem for property testing, Computational Complexity, 27 (2018), 671-716. 

[17]

Chekuri C, Jayram T S, Vondrák J. On multiplicative weight updates for concave and submodular function maximization. In Proceedings of the 6th Innovations in Theoretical Computer Science, pp. 201-210 (2015) doi: 10.1145/2688073.2688086.

[18]

Chekuri C, Quanrud K. Submodular function maximization in parallel via the multilinear relaxation. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 303-322 (2019) doi: 10.1137/1.9781611975482.20.

[19]

Chekuri C, Vondrák J, Zenklusen R. Dependent randomized rounding for matroid polytopes and applications. In Proceedings of the 51st Annual Symposium on Foundations of Computer Science, pp. 575-584 (2010)

[20]

C ChekuriJ Vondrák and R Zenklusen, Submodular function maximization via the multilinear relaxation and contention resolution schemes, SIAM Journal on Computing, 43 (2014), 1831-1879. 

[21]

X ChenRA ServedioLY TanE Waingarten and J Xie, Settling the query complexity of non-adaptive junta testing, Journal of the ACM, 65 (2018), 1-18. 

[22]

R Cole, Parallel merge sort, SIAM Journal on Computing, 17 (1988), 770-785. 

[23]

M Conforti and G Cornuéjols, Submodular set functions, matroids and the greedy algorithm: tight worst-case bounds and some generalizations of the Rado-Edmonds theorem, Journal of Discrete Applied Mathematics, 7 (1984), 251-274. 

[24]

Das A, Kempe D. Submodular meets Spectral: Greedy Algorithms for Subset Selection, Sparse Approximation and Dictionary Selection. In Proceedings of the 28th International Conference on Machine Learning, pp. 1057-1064 (2011)

[25]

NR DevanurZ HuangN KorulaVS Mirrokni and Q Yan, Whole-page optimization and submodular welfare maximization with online bidders, Journal of ACM Transactions on Economics and Computation, 4 (2016), 1-20. 

[26]

Edmonds J. Submodular Functions, Matroids, and Certain Polyhedra. Combinatorial Optimization, Volume 2570, pp. 11-26 (2003) doi: 10.1007/3-540-36478-1_2.

[27]

Ene A, Nguyen HL. Submodular maximization with nearly-optimal approximation and adaptivity in nearly-linear time. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 274-282 (2019) doi: 10.1137/1.9781611975482.18.

[28]

Fahrbach M, Mirrokni V, Zadimoghaddam M. Submodular maximization with optimal approximation, adaptivity and query complexity. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 255-273 (2019) doi: 10.1137/1.9781611975482.17.

[29]

U FeigeV S Mirrokni and J Vondrák, Maximizing non-monotone submodular functions, SIAM Journal on Computing, 40 (2011), 1133-1153. 

[30]

Feldman M, Naor J, Schwartz R. A unified continuous greedy algorithm for submodular maximization. In Proceedings of the 52nd Annual Symposium on Foundations of Computer Science, pp. 570-579 (2011) doi: 10.1109/FOCS.2011.46.

[31]

Y Filmus and J Ward, Monotone submodular maximization over a matroid via non-oblivious local search, SIAM Journal on Computing, 43 (2014), 514-542. 

[32]

Filmus Y, Ward J. The power of local search: Maximum coverage over a matroid. In Proceedings of the 29th Annual Symposium on Theoretical Aspects of Computer Science, 14: 601-612 (2012)

[33]

JD FrazierPK Jimack and RM Kirby, On the use of adjoint-based sensitivity estimates to control local mesh refinement, Communications in Computational Physics, 7 (2010), 631-8. 

[34]

S GongQ NongW Liu and Q Fang, Parametric monotone function maximization with matroid constraints, Journal of Global Optimization, 75 (2019), 833-849. 

[35]

Haupt JD, Baraniuk RG, Castro RM, Nowak RD. Compressive distilled sensing: Sparse recovery using adaptivity in compressive measurements. In Proceedings of the 43rd Asilomar Conference on Signals, Systems and Computers, pp. 1551-1555 (2009)

[36]

Haupt J, Nowak R, Castro R. Adaptive sensing for sparse signal recovery. In Proceedings of the 13th Digital Signal Processing Workshop and 5th IEEE Signal Processing Education Workshop, pp. 702-707 (2009)

[37]

R HerbrichN Lawrence and M Seeger, Fast sparse gaussian process methods: the informative vector machine, Advances in Neural Information Processing System, 15 (2003), 625-632. 

[38]

DS Hochbaum, An efficient algorithm for image segmentation, Markov random fields and related problems, Journal of the ACM, 48 (2001), 686-701. 

[39]

Indyk P, Price E, Woodruff DP. On the power of adaptivity in sparse recovery. In Proceedings of the 52nd Annual Symposium on Foundations of Computer Science, pp. 285-294 (2011) doi: 10.1109/FOCS.2011.83.

[40]

RM KarpE Upfal and A Wigderson, The complexity of parallel search, Journal of Computing System Sciences, 36 (1988), 225-253. 

[41]

Kempe D, Kleinberg JM, Tardos E. Maximizing the spread of influence through a social network. In Proceedings of the 9th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 137-146 (2003)

[42]

Krause A, Guestrin C. Near-optimal nonmyopic value of information in graphical models. In Proceedings of the 21st Conference in Uncertainty in Artificial Intelligence, pp. 324-331 (2005)

[43]

Krause A, Guestrin C. Near-optimal observation selection using submodular functions. In Proceedings of the 32nd AAAI Conference on Artificial Intelligence, pp. 1650-1654 (2007)

[44]

A KrauseA Singh and C Guestrin, Nearoptimal sensor placements in gaussian processes: theory, efficient algorithms and empirical studies, Journal of Machine Learning Research, 9 (2008), 235-284. 

[45]

Kuhnle A, Smith JD, Crawford VG, Thai MT, Fast maximization of Non-submodular, Monotonic Functions on the Integer Lattice. In Proceedings of the 35th International Conference on Machine Learning, pp. 2786-2795 (2018)

[46]

B LehmannD Lehmann and N Nisan, Combinatorial auctions with decreasing marginal utilities, Games and Economic Behavior, 55 (2006), 270-296. 

[47]

Lin H, Bilmes JA. A class of submodular functions for document summarization. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, pp. 510-520 (2011)

[48]

B Lin and M Hu, Fast algorithms for maximizing monotone nonsubmodular functions, Journal of Combinatorial Optimization, (2021). 

[49]

GL Nemhauser and LA Wolsey, Best algorithms for approximating the maximum of a submodular set function, Mathematics of Operations Research, 3 (1978), 177-188. 

[50]

GL NemhauserLA Wolsey and ML Fisher, An analysis of approximations for maximizing submodular set functions–I, Mathematical Programming, 14 (1978), 265-294. 

[51]

Nisan N, Widgerson A. Rounds in communication complexity revisited. In Proceedings of the 23rd Annual ACM Symposium on Theory of computing, pp. 419-429 (1991) doi: 10.1137/0222016.

[52]

Nong Q, Sun T, Gong S, Fang Q, Du D, Shao X. Maximize a monotone function with a generic submodularity ratio. Journal of Theoretical Computer Science https://doi.org/10.1016/j.tcs.2020.05.018 (2020)

[53]

CH Papadimitriou and M Sipser, Communication complexity, Journal of Computer and System Sciences, 28 (1984), 260-269. 

[54]

Rafiey A, Yoshida Y. Fast and Private Submodular and $k$-Submodular Functions Maximization with Matroid Constraints. In Proceedings of the 37th International Conference on Machine Learning, pp. 7887-7897 (2020)

[55]

Singla A, Tschiatschek S, Krause A. Noisy submodular maximization via adaptive sampling with applications to crowdsourced image collection summarization. In Proceedings of the 30th AAAI Conference on Artificial Intelligence, pp. 2037-2043 (2016)

[56]

Streeter MJ, Golovin D. An online algorithm for maximizing submodular functions. In Proceedings of the 22nd International Conference on Advances in Neural Information Processing Systems, pp. 1577-1584 (2008)

[57]

Sun X, Xu D, Guo L, Li M. Approximation Guarantees for Deterministic Maximization of Submodular Function with a Matroid Constraint. In Proceedings of the 16th International Conference on Theory and Applications of Models of Computation (TAMC), pp. 205-214 (2020) doi: 10.1007/978-3-030-59267-7_18.

[58]

M SviridenkoJ Vondrák and J. Ward, Optimal approximation for submodular and supermodular optimization with bounded curvature, Mathematics of Operations Research, 42 (2017), 1197-1218. 

[59]

Vondrák J. Optimal approximation for the submodular welfare problem in the value oracle model. In Proceedings of the 40th Annual ACM symposium on Theory of computing, pp. 67-74 (2008) doi: 10.1145/1374376.1374389.

[1]

Lu Han, Min Li, Dachuan Xu, Dongmei Zhang. Stochastic-Lazier-Greedy Algorithm for monotone non-submodular maximization. Journal of Industrial and Management Optimization, 2021, 17 (5) : 2607-2614. doi: 10.3934/jimo.2020085

[2]

Gaidi Li, Zhen Wang, Dachuan Xu. An approximation algorithm for the $k$-level facility location problem with submodular penalties. Journal of Industrial and Management Optimization, 2012, 8 (3) : 521-529. doi: 10.3934/jimo.2012.8.521

[3]

Jian Sun, Haiyun Sheng, Yuefang Sun, Donglei Du, Xiaoyan Zhang. Approximation algorithm with constant ratio for stochastic prize-collecting Steiner tree problem. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021116

[4]

Fengmin Wang, Dachuan Xu, Donglei Du, Chenchen Wu. Primal-dual approximation algorithms for submodular cost set cover problems with linear/submodular penalties. Numerical Algebra, Control and Optimization, 2015, 5 (2) : 91-100. doi: 10.3934/naco.2015.5.91

[5]

Laetitia Paoli. A proximal-like algorithm for vibro-impact problems with a non-smooth set of constraints. Conference Publications, 2011, 2011 (Special) : 1186-1195. doi: 10.3934/proc.2011.2011.1186

[6]

Dubi Kelmer. Approximation of points in the plane by generic lattice orbits. Journal of Modern Dynamics, 2017, 11: 143-153. doi: 10.3934/jmd.2017007

[7]

Jean-François Babadjian, Clément Mifsud, Nicolas Seguin. Relaxation approximation of Friedrichs' systems under convex constraints. Networks and Heterogeneous Media, 2016, 11 (2) : 223-237. doi: 10.3934/nhm.2016.11.223

[8]

Zheng-Hai Huang, Jie Sun. A smoothing Newton algorithm for mathematical programs with complementarity constraints. Journal of Industrial and Management Optimization, 2005, 1 (2) : 153-170. doi: 10.3934/jimo.2005.1.153

[9]

Weihua Liu, Andrew Klapper. AFSRs synthesis with the extended Euclidean rational approximation algorithm. Advances in Mathematics of Communications, 2017, 11 (1) : 139-150. doi: 10.3934/amc.2017008

[10]

Jon Chaika, Howard Masur. There exists an interval exchange with a non-ergodic generic measure. Journal of Modern Dynamics, 2015, 9: 289-304. doi: 10.3934/jmd.2015.9.289

[11]

Antonio Algaba, María Díaz, Cristóbal García, Jaume Giné. Analytic integrability around a nilpotent singularity: The non-generic case. Communications on Pure and Applied Analysis, 2020, 19 (1) : 407-423. doi: 10.3934/cpaa.2020021

[12]

Yongchao Liu, Hailin Sun, Huifu Xu. An approximation scheme for stochastic programs with second order dominance constraints. Numerical Algebra, Control and Optimization, 2016, 6 (4) : 473-490. doi: 10.3934/naco.2016021

[13]

M. Delgado Pineda, E. A. Galperin, P. Jiménez Guerra. MAPLE code of the cubic algorithm for multiobjective optimization with box constraints. Numerical Algebra, Control and Optimization, 2013, 3 (3) : 407-424. doi: 10.3934/naco.2013.3.407

[14]

Chunlin Hao, Xinwei Liu. Global convergence of an SQP algorithm for nonlinear optimization with overdetermined constraints. Numerical Algebra, Control and Optimization, 2012, 2 (1) : 19-29. doi: 10.3934/naco.2012.2.19

[15]

Alberto Bressan, Ke Han, Franco Rampazzo. On the control of non holonomic systems by active constraints. Discrete and Continuous Dynamical Systems, 2013, 33 (8) : 3329-3353. doi: 10.3934/dcds.2013.33.3329

[16]

David Julitz. Numerical approximation of atmospheric-ocean models with subdivision algorithm. Discrete and Continuous Dynamical Systems, 2007, 18 (2&3) : 429-447. doi: 10.3934/dcds.2007.18.429

[17]

Zhenbo Wang. Worst-case performance of the successive approximation algorithm for four identical knapsacks. Journal of Industrial and Management Optimization, 2012, 8 (3) : 651-656. doi: 10.3934/jimo.2012.8.651

[18]

Fabián Crocce, Ernesto Mordecki. A non-iterative algorithm for generalized pig games. Journal of Dynamics and Games, 2018, 5 (4) : 331-341. doi: 10.3934/jdg.2018020

[19]

Yong Wang, Wanquan Liu, Guanglu Zhou. An efficient algorithm for non-convex sparse optimization. Journal of Industrial and Management Optimization, 2019, 15 (4) : 2009-2021. doi: 10.3934/jimo.2018134

[20]

Vladislav Kibkalo, Tomoo Yokoyama. Topological characterizations of Morse-Smale flows on surfaces and generic non-Morse-Smale flows. Discrete and Continuous Dynamical Systems, 2022  doi: 10.3934/dcds.2022072

2021 Impact Factor: 1.411

Metrics

  • PDF downloads (146)
  • HTML views (75)
  • Cited by (0)

Other articles
by authors

[Back to Top]