{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:52Z","timestamp":1740109312110,"version":"3.37.3"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"12","license":[{"start":{"date-parts":[[2022,6,8]],"date-time":"2022-06-08T00:00:00Z","timestamp":1654646400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,6,8]],"date-time":"2022-06-08T00:00:00Z","timestamp":1654646400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"name":"Research Innovation and Knowledge Management Department of Education and Knowledge Abu Dhabi","award":["AARE18-152"],"award-info":[{"award-number":["AARE18-152"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,12]]},"DOI":"10.1007\/s00453-022-00987-z","type":"journal-article","created":{"date-parts":[[2022,6,8]],"date-time":"2022-06-08T11:03:57Z","timestamp":1654686237000},"page":"3622-3654","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Approximation Algorithms for Cost-robust Discrete Minimization Problems Based on their LP-Relaxations"],"prefix":"10.1007","volume":"84","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7652-7202","authenticated-orcid":false,"given":"Khaled","family":"Elbassioni","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,6,8]]},"reference":[{"issue":"3","key":"987_CR1","doi-asserted-by":"publisher","first-page":"1799","DOI":"10.1137\/15M1007070","volume":"26","author":"A Agra","year":"2016","unstructured":"Agra, A., Santos, M., Nace, D., Poss, M.: A dynamic programming approach for a class of robust optimization problems. SIAM J. Optim. 26(3), 1799\u20131823 (2016)","journal-title":"SIAM J. Optim."},{"issue":"4","key":"987_CR2","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/s10288-013-0231-6","volume":"11","author":"E \u00c1lvarez-Miranda","year":"2013","unstructured":"\u00c1lvarez-Miranda, E., Ljubi\u0107, I., Toth, P.: A note on the Bertsimas & Sim algorithm for robust combinatorial optimization problems. 4OR 11(4), 349\u2013360 (2013)","journal-title":"4OR"},{"issue":"1","key":"987_CR3","doi-asserted-by":"publisher","first-page":"533","DOI":"10.4086\/toc.2012.v008a024","volume":"8","author":"N Bansal","year":"2012","unstructured":"Bansal, N., Korula, N., Nagarajan, V., Srinivasan, A.: Solving packing integer programs via randomized rounding with alterations. Theory Comput. 8(1), 533\u2013565 (2012)","journal-title":"Theory Comput."},{"issue":"1","key":"987_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.4086\/toc.2018.v014a014","volume":"14","author":"A Bazzi","year":"2018","unstructured":"Bazzi, A., Fiorini, S., Huang, S., Svensson, O.: Small extended formulation for knapsack cover inequalities from monotone circuits. Theory Comput. 14(1), 1\u201329 (2018)","journal-title":"Theory Comput."},{"key":"987_CR5","doi-asserted-by":"crossref","unstructured":"Ben-Tal, A., El Ghaoui, L., Nemirovski, A.S.: Robust Optimization. Princeton Series in Applied Mathematics. Princeton University Press (2009)","DOI":"10.1515\/9781400831050"},{"key":"987_CR6","doi-asserted-by":"crossref","unstructured":"Ben-Tal, A., Nemirovski, A.: Robust convex optimization. Math. Oper. Res. 23(4), 769\u2013805 (1998)","DOI":"10.1287\/moor.23.4.769"},{"issue":"3","key":"987_CR7","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1007\/s101070100286","volume":"92","author":"A Ben-Tal","year":"2002","unstructured":"Ben-Tal, A., Nemirovski, A.: Robust optimization - methodology and applications. Math. Program. 92(3), 453\u2013480 (2002)","journal-title":"Math. Program."},{"issue":"3","key":"987_CR8","doi-asserted-by":"publisher","first-page":"464","DOI":"10.1137\/080734510","volume":"53","author":"D Bertsimas","year":"2011","unstructured":"Bertsimas, D., Brown, D., Caramanis, C.: Theory and applications of robust optimization. SIAM Rev. 53(3), 464\u2013501 (2011)","journal-title":"SIAM Rev."},{"issue":"1","key":"987_CR9","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/s10107-003-0396-4","volume":"98","author":"D Bertsimas","year":"2003","unstructured":"Bertsimas, D., Sim, M.: Robust discrete optimization and network flows. Math. Program. 98(1), 49\u201371 (2003)","journal-title":"Math. Program."},{"key":"987_CR10","unstructured":"Bertsimas, D., Sim, M.: Robust discrete optimization under ellipsoidal uncertainty sets. Technical report, Technical report, MIT (2004)"},{"issue":"1\u20132","key":"987_CR11","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1007\/s10107-005-0677-1","volume":"107","author":"D Bertsimas","year":"2006","unstructured":"Bertsimas, D., Sim, M.: Tractable approximations to robust conic optimization problems. Math. Program. 107(1\u20132), 5\u201336 (2006)","journal-title":"Math. Program."},{"issue":"3","key":"987_CR12","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1016\/j.orl.2007.09.003","volume":"36","author":"D Bienstock","year":"2008","unstructured":"Bienstock, D.: Approximate formulations for 0\u20131 knapsack sets. Oper. Res. Lett. 36(3), 317\u2013320 (2008)","journal-title":"Oper. Res. Lett."},{"key":"987_CR13","doi-asserted-by":"crossref","unstructured":"Birge, J.R., Louveaux, F.: Introduction to Stochastic Programming, 2nd edn. Springer Publishing Company, Incorporated (2011)","DOI":"10.1007\/978-1-4614-0237-4"},{"key":"987_CR14","doi-asserted-by":"crossref","unstructured":"Bougeret, M., Pessoa, A.A., Poss, M.: Robust scheduling with budgeted uncertainty. Discret. Appl. Math. 261, 93\u2013107 (2019)","DOI":"10.1016\/j.dam.2018.07.001"},{"issue":"1","key":"987_CR15","doi-asserted-by":"publisher","first-page":"10:1","DOI":"10.1145\/3355400","volume":"16","author":"B Brubach","year":"2020","unstructured":"Brubach, B., Sankararaman, K.A., Srinivasan, A., Xu, P.: Algorithms to approximate column-sparse packing problems. ACM Trans. Algorithms 16(1), 10:1-10:32 (2020)","journal-title":"ACM Trans. Algorithms"},{"issue":"3","key":"987_CR16","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1002\/rsa.10033","volume":"20","author":"RD Carr","year":"2002","unstructured":"Carr, R.D., Vempala, S.: Randomized metarounding. Random Struct. Algorithms 20(3), 343\u2013352 (2002)","journal-title":"Random Struct. Algorithms"},{"issue":"3","key":"987_CR17","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1287\/opre.1090.0741","volume":"58","author":"E Delage","year":"2010","unstructured":"Delage, E., Ye, Y.: Distributionally robust optimization under moment uncertainty with application to data-driven problems. Oper. Res. 58(3), 595\u2013612 (2010)","journal-title":"Oper. Res."},{"key":"987_CR18","unstructured":"Dhamdhere, K., Goyal, V., Ravi, R., Singh, M.: How to pay, come what may: Approximation algorithms for demand-robust covering problems. In FOCS"},{"key":"987_CR19","doi-asserted-by":"crossref","unstructured":"Dinur, I., Steurer, D.: Analytical approach to parallel repetition. In: Shmoys, D.B. (ed.) Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 624\u2013633. ACM (2014)","DOI":"10.1145\/2591796.2591884"},{"issue":"1","key":"987_CR20","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1137\/S1052623496305717","volume":"9","author":"L El Ghaoui","year":"1998","unstructured":"El Ghaoui, L., Oustry, F., Lebret, H.: Robust solutions to uncertain semidefinite programs. SIAM J. Optim. 9(1), 33\u201352 (1998)","journal-title":"SIAM J. Optim."},{"key":"987_CR21","doi-asserted-by":"crossref","unstructured":"Elbassioni, K., Makino, K., Najy, W.: A multiplicative weight updates algorithm for packing and covering semi-infinite linear programs. Algorithmica (2019)","DOI":"10.1007\/s00453-018-00539-4"},{"issue":"4","key":"987_CR22","doi-asserted-by":"publisher","first-page":"641","DOI":"10.1007\/s00224-016-9704-2","volume":"59","author":"K Elbassioni","year":"2016","unstructured":"Elbassioni, K., Mehlhorn, K., Ramezani, F.: Towards more practical linear programming-based techniques for algorithmic mechanism design. Theory Comput. Syst. 59(4), 641\u2013663 (2016)","journal-title":"Theory Comput. Syst."},{"issue":"3","key":"987_CR23","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1016\/j.disopt.2007.10.001","volume":"4","author":"B Escoffier","year":"2007","unstructured":"Escoffier, B., Hammer, P.L.: Approximation of the quadratic set covering problem. Discret. Optim. 4(3), 378\u2013386 (2007)","journal-title":"Discret. Optim."},{"key":"987_CR24","unstructured":"Feige, U., Feldman, M., Talgam-Cohen, I.: Oblivious Rounding and the Integrality Gap. In: APPROX\/RANDOM 2016, volume\u00a060, pages 8:1\u20138:23 (2016)"},{"key":"987_CR25","doi-asserted-by":"crossref","unstructured":"Feige, U., Jain, K., Mahdian, M., Mirrokni, V.: Robust combinatorial optimization with exponential scenarios. In: IPCO, pages 439\u2013453 (2007)","DOI":"10.1007\/978-3-540-72792-7_33"},{"key":"987_CR26","doi-asserted-by":"crossref","unstructured":"Goetzmann, K.-S., Stiller, S., Telha, C.: Optimization over integers with robustness in cost and few constraints. In: WAOA, pages 89\u2013101 (2012)","DOI":"10.1007\/978-3-642-29116-6_8"},{"key":"987_CR27","doi-asserted-by":"crossref","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization, volume\u00a02 of Algorithms and Combinatorics. Springer, second corrected edition (1993)","DOI":"10.1007\/978-3-642-78240-4"},{"issue":"3","key":"987_CR28","doi-asserted-by":"publisher","first-page":"731","DOI":"10.1287\/opre.2019.1853","volume":"67","author":"L Hellerstein","year":"2019","unstructured":"Hellerstein, L., Lidbetter, T., Pirutinsky, D.: Solving zero-sum games using best-response oracles with applications to search games. Oper. Res. 67(3), 731\u2013743 (2019)","journal-title":"Oper. Res."},{"key":"987_CR29","unstructured":"Ilyina, A.: Combinatorial optimization under ellipsoidal uncertainty. Technischen Universit\u00e4t Dortmund. Ph.D. Thesis (2017)"},{"issue":"1\u20133","key":"987_CR30","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/S0304-3975(02)00829-0","volume":"302","author":"K Jansen","year":"2003","unstructured":"Jansen, K.: Approximate strong separation with application in fractional graph coloring and preemptive scheduling. Theor. Comput. Sci. 302(1\u20133), 239\u2013256 (2003)","journal-title":"Theor. Comput. Sci."},{"key":"987_CR31","doi-asserted-by":"crossref","unstructured":"Kawase, Y., Sumita, H.: Randomized strategies for robust combinatorial optimization. In: The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019, The Thirty-First Innovative Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019, Honolulu, Hawaii, USA, January 27 - February 1, 2019, pages 7876\u20137883. AAAI Press (2019)","DOI":"10.1609\/aaai.v33i01.33017876"},{"issue":"4","key":"987_CR32","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1016\/j.jcss.2005.05.002","volume":"71","author":"SG Kolliopoulos","year":"2005","unstructured":"Kolliopoulos, S.G., Young, N.E.: Approximation algorithms for covering\/packing integer programs. J. Comput. Syst. Sci. 71(4), 495\u2013505 (2005)","journal-title":"J. Comput. Syst. Sci."},{"key":"987_CR33","doi-asserted-by":"crossref","unstructured":"Kraft, D., Fadaei, S., Bichler, M.: Fast convex decomposition for truthful social welfare approximation. In: Liu, Tie-Yan, Qi, Qi, Ye, Yinyu (eds.) Web and Internet Economics - 10th International Conference, WINE 2014, Beijing, China, December 14-17, 2014. Proceedings, volume 8877 of Lecture Notes in Computer Science, pages 120\u2013132. Springer (2014)","DOI":"10.1007\/978-3-319-13129-0_9"},{"issue":"2","key":"987_CR34","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1137\/S0097539793250767","volume":"26","author":"A Panconesi","year":"1997","unstructured":"Panconesi, A., Srinivasan, A.: Randomized distributed edge coloring via an extension of the chernoff-hoeffding bounds. SIAM J. Comput. 26(2), 350\u2013368 (1997)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"987_CR35","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1002\/net.21615","volume":"66","author":"AA Pessoa","year":"2015","unstructured":"Pessoa, A.A., Pugliese, L.D.P., Guerriero, F., Poss, M.: Robust constrained shortest path problems under budgeted uncertainty. Networks 66(2), 98\u2013111 (2015)","journal-title":"Networks"},{"key":"987_CR36","unstructured":"Poss, M.: Contributions to robust combinatorial optimization with budgeted uncertainty. Universit\u00e9 de Montpellier. Oper- ations Research [cs.RO], 2016. tel-01421260"},{"key":"987_CR37","unstructured":"Pritchard, D.: An LP with integrality gap 1+epsilon for multidimensional knapsack. CoRR, arXiv:1005.3324 (2010)"},{"issue":"2","key":"987_CR38","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1016\/j.ejor.2018.01.054","volume":"268","author":"B Rostami","year":"2018","unstructured":"Rostami, B., Chassein, A.B., Hopf, M., Frey, D., Buchheim, C., Malucelli, F., Goerigk, M.: The quadratic shortest path problem: complexity, approximability, and solution methods. Eur. J. Oper. Res. 268(2), 473\u2013485 (2018)","journal-title":"Eur. J. Oper. Res."},{"issue":"2","key":"987_CR39","doi-asserted-by":"publisher","first-page":"648","DOI":"10.1137\/S0097539796314240","volume":"29","author":"A Srinivasan","year":"1999","unstructured":"Srinivasan, A.: Improved approximation guarantees for packing and covering integer programs. SIAM J. Comput. 29(2), 648\u2013670 (1999)","journal-title":"SIAM J. Comput."},{"key":"987_CR40","volume-title":"Approximation Algorithms","author":"VV Vazirani","year":"2001","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer-Verlag, Berlin, Heidelberg (2001)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00987-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-00987-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00987-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,28]],"date-time":"2022-11-28T12:11:59Z","timestamp":1669637519000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-00987-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,8]]},"references-count":40,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["987"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-00987-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2022,6,8]]},"assertion":[{"value":"19 March 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 May 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 June 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}