{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T15:35:17Z","timestamp":1742916917326,"version":"3.40.3"},"publisher-location":"Cham","reference-count":35,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031434204"},{"type":"electronic","value":"9783031434211"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023]]},"DOI":"10.1007\/978-3-031-43421-1_19","type":"book-chapter","created":{"date-parts":[[2023,9,17]],"date-time":"2023-09-17T20:37:24Z","timestamp":1694983044000},"page":"316-332","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Scalable Solution for\u00a0the\u00a0Extended Multi-channel Facility Location Problem"],"prefix":"10.1007","author":[{"given":"Etika","family":"Agarwal","sequence":"first","affiliation":[]},{"given":"Karthik S.","family":"Gurumoorthy","sequence":"additional","affiliation":[]},{"given":"Ankit Ajit","family":"Jain","sequence":"additional","affiliation":[]},{"given":"Shantala","family":"Manchenahally","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,9,18]]},"reference":[{"key":"19_CR1","unstructured":"Abid, B.K., Gower, R.: Stochastic algorithms for entropy-regularized optimal transport problems. In: Proceedings of the 21st International Conference on Artificial Intelligence and Statistics, vol. 84, pp. 1505\u20131512. PMLR (2018)"},{"key":"19_CR2","unstructured":"Altschuler, J., Niles-Weed, J., Rigollet, P.: Near-linear time approximation algorithms for optimal transport via sinkhorn iteration. In: Proceedings of the 31st Conference on Neural Information Processing Systems, vol. 30, pp. 1964\u20131974 (2017)"},{"key":"19_CR3","doi-asserted-by":"crossref","unstructured":"Arya, V., Garg, N., Khandekar, R., Meyerson, A., Mungala, K., Pandit, V.: Local search heuristic for K-median and facility location problems. In: 33rd ACM Symposium on Theory of Computing, pp. 21\u201329 (2001)","DOI":"10.1145\/380752.380755"},{"key":"19_CR4","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1007\/BF02680552","volume":"83","author":"F Barahona","year":"1998","unstructured":"Barahona, F., Jensen, D.: Plant location with minimum inventory. Math. Program. 83, 101\u2013111 (1998)","journal-title":"Math. Program."},{"key":"19_CR5","doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Feldman, M., Naor, J.S., Schwartz, R.: Submodular maximization with cardinality constraints. In: 25th ACM-SIAM Symposium on Discrete Algorithms, pp. 1433\u20131452 (2014)","DOI":"10.1137\/1.9781611973730.80"},{"issue":"2","key":"19_CR6","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1287\/moor.2016.0809","volume":"42","author":"N Buchbinder","year":"2017","unstructured":"Buchbinder, N., Feldman, M., Schwartz, R.: Comparing apples and oranges: query trade-off in submodular maximization. Math. Oper. Res. 42(2), 308\u2013329 (2017)","journal-title":"Math. Oper. Res."},{"key":"19_CR7","unstructured":"Charikar, M., Guha, S.: Improved combinatorial algorithms for facility location and K-median problems. In: 40th Annual Symposium on Foundations of Computer Science (1999)"},{"key":"19_CR8","doi-asserted-by":"crossref","unstructured":"Chudak, F., Shmoys, D.: Improved approximation algorithms for the capacitated facility location problem. In: 10th ACM-SIAM Symposium on Discrete Algorithms (1999)","DOI":"10.1007\/3-540-48777-8_8"},{"key":"19_CR9","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/s10107-004-0524-9","volume":"102","author":"F Chudak","year":"2005","unstructured":"Chudak, F., Williamson, D.: Improved approximation algorithms for capacitated facility location problems. Math. Program. 102, 207\u2013222 (2005)","journal-title":"Math. Program."},{"key":"19_CR10","unstructured":"Cuturi, M.: Sinkhorn distances: lightspeed computation of optimal transport. In: Advances in Neural Information Processing Systems, vol. 26 (2013)"},{"key":"19_CR11","doi-asserted-by":"crossref","unstructured":"Shmoys, D., Tardos, \u00c9., Aardal, K.: Approximation algorithms for the facility location problems. In: 29th ACM Symposium on Theory of Computing, pp. 265\u2013274 (1997)","DOI":"10.1145\/258533.258600"},{"key":"19_CR12","unstructured":"Dvurechensky, P., Gasnikov, A., Kroshnin, A.: Computational optimal transport: Complexity by accelerated gradient descent is better than by Sinkhorn\u2019s algorithm. In: Proceedings of the 35th International Conference on Machine Learning, vol. 80, pp. 1367\u20131376. PMLR (2018)"},{"key":"19_CR13","doi-asserted-by":"publisher","first-page":"3539","DOI":"10.1214\/17-AOS1679","volume":"46","author":"E Elenberg","year":"2018","unstructured":"Elenberg, E., Khanna, R., Dimakis, A.G., Negahban, S.: Restricted strong convexity implies weak submodularity. Ann. Stat. 46, 3539\u20133568 (2018)","journal-title":"Ann. Stat."},{"key":"19_CR14","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/BF01585521","volume":"7","author":"AM Frieze","year":"1974","unstructured":"Frieze, A.M.: A cost function property for plant location problems. Math. Program. 7, 245\u2013248 (1974)","journal-title":"Math. Program."},{"key":"19_CR15","volume-title":"Submodular Functions and Optimization","author":"S Fujishige","year":"2005","unstructured":"Fujishige, S.: Submodular Functions and Optimization. Elsevier, Amsterdam (2005)"},{"key":"19_CR16","volume-title":"The Uncapacitated Facility Location Problem","author":"G Cornu\u00e9jols","year":"1990","unstructured":"Cornu\u00e9jols, G., Nemhauser, G., Wolsey, L.: The Uncapacitated Facility Location Problem. Wiley, New York (1990)"},{"key":"19_CR17","doi-asserted-by":"crossref","unstructured":"Gurumoorthy, K.S., Dhurandhar, A., Cecchi, G., Aggarwal, C.: Efficient data representation by selecting prototypes with importance weights. In: IEEE ICDM (2019)","DOI":"10.1109\/ICDM.2019.00036"},{"key":"19_CR18","unstructured":"Harshaw, C., Feldman, M., Ward, J., Karbasi, A.: Submodular maximization beyond non-negativity: guarantees, fast algorithms, and applications. In: 36 International Conference on Machine Learning (2019)"},{"key":"19_CR19","unstructured":"Jain, K., Vazirani, V.: Primal-dual approximation algorithms for metric facility location and K-median problems. In: 40th Annual Symposium on Foundations of Computer Science (1999)"},{"key":"19_CR20","first-page":"199","volume":"37","author":"L Kantorovich","year":"1942","unstructured":"Kantorovich, L.: On the translocation of masses. Doklady Acad. Sci. USSR 37, 199\u2013201 (1942)","journal-title":"Doklady Acad. Sci. USSR"},{"issue":"4","key":"19_CR21","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/BF02579150","volume":"4","author":"N Karmarkar","year":"1984","unstructured":"Karmarkar, N.: A new polynomial-time algorithm for linear programming. Combinatorica 4(4), 373\u2013395 (1984)","journal-title":"Combinatorica"},{"issue":"5","key":"19_CR22","first-page":"1093","volume":"224","author":"L Khachiyan","year":"1979","unstructured":"Khachiyan, L.: A polynomial algorithm for linear programming. Doklady Akademii Nauk SSSR 224(5), 1093\u20131096 (1979)","journal-title":"Doklady Akademii Nauk SSSR"},{"issue":"1","key":"19_CR23","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1137\/060659624","volume":"30","author":"PA Knight","year":"2008","unstructured":"Knight, P.A.: The Sinkhorn-Knopp algorithm: convergence and applications. SIAM J. Matrix Anal. Appl. 30(1), 261\u2013275 (2008)","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"19_CR24","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1006\/jagm.2000.1100","volume":"37","author":"M Korupolu","year":"2000","unstructured":"Korupolu, M., Plaxton, C., Rajaraman, R.: Analysis of a local search heuristic for facility location problems. J. Algorithms 37, 146\u2013188 (2000)","journal-title":"J. Algorithms"},{"key":"19_CR25","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1287\/mnsc.9.4.643","volume":"9","author":"AA Kuehn","year":"1963","unstructured":"Kuehn, A.A., Hamburger, M.J.: A heuristic program for locating warehouses. Manage. Sci. 9, 643\u2013666 (1963)","journal-title":"Manage. Sci."},{"key":"19_CR26","unstructured":"Kuhnle, A.: Interlaced greedy algorithm for maximization of submodular functions in nearly linear time. In: Advances in Neural Information Processing Systems, vol. 32 (2019)"},{"key":"19_CR27","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/978-3-642-68874-4_10","volume-title":"Mathematical Programming - The State of the Art","author":"L Lov\u00e1sz","year":"1983","unstructured":"Lov\u00e1sz, L.: Submodular functions and convexit. In: Bachem, A., Korte, B., Gr\u00f6tschel, M. (eds.) Mathematical Programming - The State of the Art, pp. 235\u2013257. Springer, Heidelberg (1983). https:\/\/doi.org\/10.1007\/978-3-642-68874-4_10"},{"key":"19_CR28","first-page":"960","volume":"41","author":"C Lund","year":"1994","unstructured":"Lund, C., Yannakakis, M.: On the hardness of approximating minimization problems. ACM 41, 960\u2013981 (1994)","journal-title":"ACM"},{"key":"19_CR29","doi-asserted-by":"crossref","unstructured":"Mahdian, M., Ye, Y., Zhang, J.: A 2-approximation algorithm for the soft-capacitated facility location problem. In: 6th International Workshop on Approximation Algorithms for Combinatorial Optimization, pp. 129\u2013140 (2003)","DOI":"10.1007\/978-3-540-45198-3_12"},{"key":"19_CR30","doi-asserted-by":"crossref","unstructured":"Mirzasoleiman, B., Badanidiyuru, A., Karbasi, A., Vondr\u00e1k, J., Krause, A.: Lazier than lazy greedy. In: Association for the Advancement of Artificial Intelligence (2015)","DOI":"10.1609\/aaai.v29i1.9486"},{"key":"19_CR31","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF01588971","volume":"14","author":"GL Nemhauser","year":"1978","unstructured":"Nemhauser, G.L., Wolsey, L.A., Fisher, M.L.: An analysis of approximations for maximizing submodular set functions. Math. Program. 14, 265\u2013294 (1978)","journal-title":"Math. Program."},{"key":"19_CR32","doi-asserted-by":"crossref","unstructured":"P\u00e1l, M., Tardos, \u00c9., Wexler, T.: Facility location with nonuniform hard capacities. In: IEEE FOCS, pp. 329\u2013338 (2001)","DOI":"10.1109\/SFCS.2001.959907"},{"issue":"5\u20136","key":"19_CR33","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1561\/2200000073","volume":"11","author":"G Peyr\u00e9","year":"2019","unstructured":"Peyr\u00e9, G., Cuturi, M.: Computational optimal transport. Found. Trends Mach. Learn. 11(5\u20136), 355\u2013607 (2019)","journal-title":"Found. Trends Mach. Learn."},{"key":"19_CR34","unstructured":"Sakaue, S.: Guarantees of stochastic greedy algorithms for non-monotone submodular maximization with cardinality constraint. In: 23rd International Conference on Artificial Intelligence and Statistics (2020)"},{"key":"19_CR35","unstructured":"Xie, Y., Luo, Y., Huo, X.: An accelerated stochastic algorithm for solving the optimal transport problem. CoRR abs\/2203.00813 (2022)"}],"container-title":["Lecture Notes in Computer Science","Machine Learning and Knowledge Discovery in Databases: Research Track"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-43421-1_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,17]],"date-time":"2023-09-17T20:44:40Z","timestamp":1694983480000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-43421-1_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031434204","9783031434211"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-43421-1_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"18 September 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"We do not foresee any scenario where our method would put a certain demographic, a specific organisation, or a particular location to a systematic disadvantage. We neither use any personal data in our experiments, nor think that our method will have policing or military applications. Our work is only focused on developing a fast, scalable algorithm to identify the set of facilities to be opened, to minimise the total cost associated with serving the demand from multiple client locations.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical Impact"}},{"value":"ECML PKDD","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Joint European Conference on Machine Learning and Knowledge Discovery in Databases","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Turin","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18 September 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 September 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ecml2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/2023.ecmlpkdd.org\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"CMT","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"829","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"196","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"24% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.63","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"4.5","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Applied Data Science Track: 239 submissions, 58 accepted papers; Demo Track: 31 submissions, 16 accepted papers.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}