×
Disser, Yann; Klimm, Max; Lutz, Annette; Weckbecker, David

Fractionally subadditive maximization under an incremental knapsack constraint with applications to incremental flows. (English) Zbl 07809680

SIAM J. Discrete Math. 38, No. 1, 764-789 (2024).
Summary: We consider the problem of maximizing a fractionally subadditive function under an increasing knapsack constraint. An incremental solution to this problem is given by an order in which to include the elements of the ground set, and the competitive ratio of an incremental solution is defined by the worst ratio over all capacities relative to an optimum solution of the corresponding capacity. We present an algorithm that finds an incremental solution of competitive ratio at most \(\max \{3.293\sqrt{M},2M\}\), under the assumption that the values of singleton sets are in the range \([1,M]\), and we give a lower bound of \(\max\{2.618,M\}\) on the attainable competitive ratio. In addition, we establish that our framework captures potential-based flows between two vertices, and we give a lower bound of \(\max\{2,M\}\) and an upper bound of \(2M\) for the incremental maximization of classical flows with capacities in \([1,M]\) which is tight for the unit capacity case.

MSC:

68W27 Online algorithms; streaming algorithms
68W40 Analysis of algorithms
90C17 Robustness in mathematical programming

Keywords:

incremental optimization; competitive analysis; fractional subadditivity; flow
Cite Review PDF
Full Text: DOI

References:

[1] Amanatidis, G., Birmpas, G., and Markakis, E., Coverage, matching, and beyond: New results on budgeted mechanism design, in Proceedings of the 12th International Conference on Web and Internet Economics (WINE), , 2016, pp. 414-428, doi:10.1007/978-3-662-54110-4_29. · Zbl 1406.91153
[2] Anari, N., Haghtalab, N., Naor, S., Pokutta, S., Singh, M., and Torrico, A., Structured robust submodular maximization: Offline and online algorithms, INFORMS J. Comput., 33 (2021), pp. 1590-1607, doi:10.1287/ijoc.2020.0998. · Zbl 07549352
[3] Badanidiyuru, A., Dobzinski, S., and Oren, S., Optimization with demand oracles, Algorithmica, 81 (2019), pp. 2244-2269, doi:10.1007/s00453-018-00532-x. · Zbl 1421.68194
[4] Bernstein, A., Disser, Y., Groß, M., and Himburg, S., General bounds for incremental maximization, Math. Program., 191 (2020), pp. 953-979, doi:10.1007/s10107-020-01576-0. · Zbl 07495406
[5] Disser, Y., Klimm, M., Megow, N., and Stiller, S., Packing a knapsack of unknown capacity, SIAM J. Discrete Math., 31 (2017), pp. 1477-1497, doi:10.1137/16M1070049. · Zbl 1370.68329
[6] Disser, Y., Klimm, M., and Weckbecker, D., Fractionally subadditive maximization under an incremental knapsack constraint, in Proceedings of the 19th Workshop on Approximation and Online Algorithms (WAOA), , 2021, pp. 206-223, doi:10.1007/978-3-030-92702-8_13. · Zbl 07603893
[7] Disser, Y. and Weckbecker, D., Unified Greedy Approximability beyond Submodular Maximization, in Proceedings of the 7th International Symposium on Combinatorial Optimization (ISCO), , 2022, pp. 299-311, doi:10.1007/978-3-031-18530-4_22. · Zbl 1528.90214
[8] Dobzinski, S., Nisan, N., and Schapira, M., Approximation algorithms for combinatorial auctions with complement-free bidders, Math. Oper. Res., 35 (2010), pp. 1-13, doi:10.1287/moor.1090.0436. · Zbl 1216.68338
[9] Dobzinski, S. and Schapira, M., An improved approximation algorithm for combinatorial auctions with submodular bidders, in Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm (SODA), , ACM, New York, 2006, pp. 1064-1073, doi:10.1145/1109557.1109675. · Zbl 1192.91102
[10] Feige, U., A threshold of ln n for approximating set cover, J. ACM, 45 (1998), pp. 634-652, doi:10.1145/285055.285059. · Zbl 1065.68573
[11] Feige, U., On maximizing welfare when utility functions are subadditive, SIAM J. Comput., 39 (2009), pp. 122-142, doi:10.1137/070680977. · Zbl 1185.68855
[12] Fujita, R., Kobayashi, Y., and Makino, K., Robust matchings and matroid intersections, SIAM J. Discrete Math., 27 (2013), pp. 1234-1256, doi:10.1137/100808800. · Zbl 1285.05136
[13] Groß, M., Pfetsch, M. E., Schewe, L., Schmidt, M., and Skutella, M., Algorithmic results for potential-based flows: Easy and hard cases, Networks, 73 (2019), pp. 306-324, doi:10.1002/net.21865. · Zbl 1418.90055
[14] Hartline, J. and Sharp, A., Incremental flow, Networks, 50 (2007), pp. 77-85, doi:10.1002/net.20168. · Zbl 1119.90007
[15] Hassin, R. and Rubinstein, S., Robust matchings, SIAM J. Discrete Math., 15 (2002), pp. 530-537, doi:10.1137/S0895480198332156. · Zbl 1006.05051
[16] Kakimura, N. and Makino, K., Robust independence systems, SIAM J. Discrete Math., 27 (2013), pp. 1257-1273, doi:10.1137/120899480. · Zbl 1290.68100
[17] Kakimura, N., Makino, K., and Seimi, K., Computing knapsack solutions with cardinality robustness, Jpn. J. Ind. Appl. Math., 29 (2012), pp. 469-483, doi:10.1007/s13160-012-0075-z. · Zbl 1258.68184
[18] Kalinowski, T., Matsypura, D., and Savelsbergh, M. W., Incremental network design with maximum flows, European J. Oper. Res., 242 (2015), pp. 51-62, doi:10.1016/j.ejor.2014.10.003. · Zbl 1341.90024
[19] Kawase, Y., Sumita, H., and Fukunaga, T., Submodular maximization with uncertain knapsack capacity, SIAM J. Discrete Math., 33 (2019), pp. 1121-1145, doi:10.1137/18M1174428. · Zbl 1437.90138
[20] Klimm, M. and Knaack, M., Maximizing a submodular function with bounded curvature under an unknown knapsack constraint, in Proceedings of the International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), , 2022, pp. 49:1-49:19, doi:10.4230/LIPIcs.APPROX/RANDOM.2022.49. · Zbl 07900633
[21] Kobayashi, Y. and Takazawa, K., Randomized strategies for cardinality robustness in the knapsack problem, Theoret. Comput. Sci., 699 (2017), pp. 53-62, doi:10.1016/j.tcs.2016.12.019. · Zbl 1380.90237
[22] Lehmann, B., Lehmann, D., and Nisan, N., Combinatorial auctions with decreasing marginal utilities, Games Econom. Behav., 55 (2006), pp. 270-296, doi:10.1016/j.geb.2005.02.006. · Zbl 1125.91043
[23] Lin, G., Nagarajan, C., Rajaraman, R., and Williamson, D. P., A general approach for incremental approximation and hierarchical clustering, SIAM J. Comput., 39 (2010), pp. 3633-3669, doi:10.1137/070698257. · Zbl 1209.68648
[24] Marchetti-Spaccamela, A. and Vercellis, C., Stochastic on-line knapsack problems, Math. Program., 68 (1995), pp. 73-104, doi:10.1007/BF01585758. · Zbl 0832.90083
[25] Matuschke, J., Skutella, M., and Soto, J. A., Robust randomized matchings, Math. Oper. Res., 43 (2018), pp. 675-692, doi:10.1287/moor.2017.0878. · Zbl 1436.91087
[26] Megow, N. and Mestre, J., Instance-sensitive robustness guarantees for sequencing with unknown packing and covering constraints, in Proceedings of the 4th Conference on Innovations in Theoretical Computer Science (ITCS), , 2013, pp. 495-504, doi:10.1145/2422436.2422490.
[27] Mirrokni, V., Schapira, M., and Vondrák, J., Tight information-theoretic lower bounds for welfare maximization in combinatorial auctions, in Proceedings of the 9th ACM Conference on Electronic Commerce, , 2008, pp. 70-77, doi:10.1145/1386790.1386805.
[28] Navarra, A. and Pinotti, C. M., Online knapsack of unknown capacity: How to optimize energy consumption in smartphones, Theoret. Comput. Sci., 697 (2017), pp. 98-109, doi:10.1016/j.tcs.2017.07.029. · Zbl 1390.90475
[29] Nemhauser, G. L., Wolsey, L. A., and Fisher, M. L., An analysis of approximations for maximizing submodular set functions—I, Math. Program., 14 (1978), pp. 265-294, doi:10.1007/BF01588971. · Zbl 0374.90045
[30] Nisan, N., Bidding and allocation in combinatorial auctions, in Proceedings of the 2nd ACM Conference on Electronic Commerce (EC), , 2000, pp. 1-12, doi:10.1145/352871.352872.
[31] Orlin, J. B., Schulz, A. S., and Udwani, R., Robust monotone submodular function maximization, Math. Program., 172 (2018), pp. 505-537, doi:10.1007/s10107-018-1320-2. · Zbl 1401.90261
[32] Singer, Y., Budget feasible mechanisms, in Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science (FOCS), , 2010, pp. 765-774, doi:10.1109/FOCS.2010.78.
[33] Sviridenko, M., A note on maximizing a submodular set function subject to a knapsack constraint, Oper. Res. Lett., 32 (2004), pp. 41-43, doi:10.1016/s0167-6377(03)00062-2. · Zbl 1056.90124
[34] Thielen, C., Tiedemann, M., and Westphal, S., The online knapsack problem with incremental capacity, Math. Methods Oper. Res., 83 (2016), pp. 207-242, doi:10.1007/s00186-015-0526-9. · Zbl 1346.90722
[35] Yoshida, Y., Maximizing a monotone submodular function with a bounded curvature under a knapsack constraint, SIAM J. Discrete Math., 33 (2019), pp. 1452-1471, doi:10.1137/16M1107644. · Zbl 1421.90133
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.