{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T18:30:18Z","timestamp":1743013818081,"version":"3.40.3"},"publisher-location":"Cham","reference-count":42,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031813955"},{"type":"electronic","value":"9783031813962"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"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":[[2025]]},"DOI":"10.1007\/978-3-031-81396-2_14","type":"book-chapter","created":{"date-parts":[[2025,2,11]],"date-time":"2025-02-11T23:14:23Z","timestamp":1739315663000},"page":"198-212","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Approximate Min-Sum Subset Convolution"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8843-3374","authenticated-orcid":false,"given":"Mihail","family":"Stoian","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,2,12]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Backurs, A., Indyk, P., Schmidt, L.: Better approximations for tree sparsity in nearly-linear time. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2215\u20132229. SIAM (2017)","key":"14_CR1","DOI":"10.1137\/1.9781611974782.145"},{"key":"14_CR2","doi-asserted-by":"publisher","first-page":"3993","DOI":"10.1007\/s00453-018-0512-8","volume":"81","author":"N Bansal","year":"2019","unstructured":"Bansal, N., Chalermsook, P., Laekhanukit, B., Nanongkai, D., Nederlof, J.: New tools and connections for exponential-time approximation. Algorithmica 81, 3993\u20134009 (2019)","journal-title":"Algorithmica"},{"doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Fourier meets m\u00f6bius: fast subset convolution. In: Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, pp. 67\u201374 (2007)","key":"14_CR3","DOI":"10.1145\/1250790.1250801"},{"issue":"2","key":"14_CR4","doi-asserted-by":"publisher","first-page":"546","DOI":"10.1137\/070683933","volume":"39","author":"A Bj\u00f6rklund","year":"2009","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Koivisto, M.: Set partitioning via inclusion-exclusion. SIAM J. Comput. 39(2), 546\u2013563 (2009). https:\/\/doi.org\/10.1137\/070683933","journal-title":"SIAM J. Comput."},{"issue":"17","key":"14_CR5","doi-asserted-by":"publisher","first-page":"1954","DOI":"10.1016\/j.dam.2011.07.009","volume":"159","author":"N Bourgeois","year":"2011","unstructured":"Bourgeois, N., Escoffier, B., Paschos, V.T.: Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms. Discret. Appl. Math. 159(17), 1954\u20131970 (2011)","journal-title":"Discret. Appl. Math."},{"doi-asserted-by":"crossref","unstructured":"Bremner, D., et al.: Necklaces, convolutions, and x+y. In: Algorithms\u2013ESA 2006: 2006 Proceedings of the 14th Annual European Symposium, Zurich, Switzerland, 11\u201313 September, pp. 160\u2013171. Springer (2006)","key":"14_CR6","DOI":"10.1007\/11841036_17"},{"doi-asserted-by":"crossref","unstructured":"Bringmann, K., K\u00fcnnemann, M., W\u0119grzycki, K.: Approximating APSP without scaling: equivalence of approximate min-plus and exact min-max. In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pp. 943\u2013954 (2019)","key":"14_CR7","DOI":"10.1145\/3313276.3316373"},{"issue":"11","key":"14_CR8","doi-asserted-by":"publisher","first-page":"1026","DOI":"10.1109\/LSP.2013.2278147","volume":"20","author":"C Cartis","year":"2013","unstructured":"Cartis, C., Thompson, A.: An exact tree projection algorithm for wavelets. IEEE Sig. Process. Lett. 20(11), 1026\u20131029 (2013). https:\/\/doi.org\/10.1109\/LSP.2013.2278147","journal-title":"IEEE Sig. Process. Lett."},{"doi-asserted-by":"crossref","unstructured":"Chan, T.M., Williams, R.: Deterministic APSP, orthogonal vectors, and more: quickly derandomizing Razborov-Smolensky. In: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1246\u20131255. SIAM (2016)","key":"14_CR9","DOI":"10.1137\/1.9781611974331.ch87"},{"key":"14_CR10","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., et al.: Parameterized Algorithms, 1st edn. Springer, Heidelberg (2015)","edition":"1"},{"doi-asserted-by":"crossref","unstructured":"Cygan, M., et\u00a0al.: Algebraic techniques: sieves, convolutions, and polynomials. In: Parameterized Algorithms, pp. 321\u2013355 (2015)","key":"14_CR11","DOI":"10.1007\/978-3-319-21275-3_10"},{"issue":"1","key":"14_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3293465","volume":"15","author":"M Cygan","year":"2019","unstructured":"Cygan, M., Mucha, M., W\u0119grzycki, K., W\u0142odarczyk, M.: On problems equivalent to (min,+)-convolution. ACM Trans. Algorithms (TALG) 15(1), 1\u201325 (2019)","journal-title":"ACM Trans. Algorithms (TALG)"},{"issue":"3","key":"14_CR13","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1002\/net.3230010302","volume":"1","author":"SE Dreyfus","year":"1971","unstructured":"Dreyfus, S.E., Wagner, R.A.: The Steiner problem in graphs. Networks 1(3), 195\u2013207 (1971)","journal-title":"Networks"},{"doi-asserted-by":"crossref","unstructured":"Duan, R., Pettie, S.: Fast algorithms for (max, min)-matrix multiplication and bottleneck shortest paths. In: Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 384\u2013391. SIAM (2009)","key":"14_CR14","DOI":"10.1137\/1.9781611973068.43"},{"doi-asserted-by":"publisher","unstructured":"Duan, R., Pettie, S., Su, H.H.: Scaling algorithms for weighted matching in general graphs. ACM Trans. Algorithms 14(1) (2018). https:\/\/doi.org\/10.1145\/3155301","key":"14_CR15","DOI":"10.1145\/3155301"},{"issue":"4\u20135","key":"14_CR16","doi-asserted-by":"publisher","first-page":"979","DOI":"10.1051\/ro\/2015060","volume":"50","author":"B Escoffier","year":"2016","unstructured":"Escoffier, B., Paschos, V.T., Tourniaire, E.: Super-polynomial approximation branching algorithms. RAIRO Oper. Res. 50(4\u20135), 979\u2013994 (2016)","journal-title":"RAIRO Oper. Res."},{"unstructured":"Esmer, B.C., Kulik, A., Marx, D., Neuen, D., Sharma, R.: Faster exponential-time approximation algorithms using approximate monotone local search. arXiv preprint arXiv:2206.13481 (2022)","key":"14_CR17"},{"unstructured":"Esmer, B.C., Kulik, A., Marx, D., Neuen, D., Sharma, R.: Approximate monotone local search for weighted problems. arXiv preprint arXiv:2308.15306 (2023)","key":"14_CR18"},{"doi-asserted-by":"crossref","unstructured":"Esmer, B.C., Kulik, A., Marx, D., Neuen, D., Sharma, R.: Optimally Repurposing Existing Algorithms to Obtain Exponential-Time Approximations, pp. 314\u2013345 (2024)","key":"14_CR19","DOI":"10.1137\/1.9781611977912.13"},{"issue":"2","key":"14_CR20","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1006\/jcss.1998.1587","volume":"57","author":"U Feige","year":"1998","unstructured":"Feige, U., Kilian, J.: Zero knowledge and the chromatic number. J. Comput. Syst. Sci. 57(2), 187\u2013199 (1998)","journal-title":"J. Comput. Syst. Sci."},{"doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms, 1st edn. Springer, Heidelberg (2010)","key":"14_CR21","DOI":"10.1007\/978-3-642-16533-7_1"},{"doi-asserted-by":"crossref","unstructured":"Frank, A., Tardos, \u00c9.: An application of simultaneous diophantine approximation in combinatorial optimization. Combinatorica 7, 49\u201365 (1987). https:\/\/api.semanticscholar.org\/CorpusID:45585308","key":"14_CR22","DOI":"10.1007\/BF02579200"},{"issue":"4","key":"14_CR23","doi-asserted-by":"publisher","first-page":"815","DOI":"10.1145\/115234.115366","volume":"38","author":"HN Gabow","year":"1991","unstructured":"Gabow, H.N., Tarjan, R.E.: Faster scaling algorithms for general graph matching problems. J. ACM (JACM) 38(4), 815\u2013853 (1991)","journal-title":"J. ACM (JACM)"},{"issue":"2","key":"14_CR24","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1016\/0022-0000(85)90039-X","volume":"31","author":"HN Garbow","year":"1985","unstructured":"Garbow, H.N.: Scaling algorithms for network problems. J. Comput. Syst. Sci. 31(2), 148\u2013168 (1985)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"14_CR25","doi-asserted-by":"publisher","first-page":"494","DOI":"10.1137\/S0097539792231179","volume":"24","author":"AV Goldberg","year":"1995","unstructured":"Goldberg, A.V.: Scaling algorithms for the shortest paths problem. SIAM J. Comput. 24(3), 494\u2013504 (1995)","journal-title":"SIAM J. Comput."},{"key":"14_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1007\/11786986_21","volume-title":"Automata, Languages and Programming","author":"S Khot","year":"2006","unstructured":"Khot, S., Ponnuswami, A.K.: Better inapproximability results for MaxClique, chromatic number and Min-3Lin-deletion. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol. 4051, pp. 226\u2013237. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11786986_21"},{"doi-asserted-by":"publisher","unstructured":"Kosaraju, S.: Efficient tree pattern matching. In: 30th Annual Symposium on Foundations of Computer Science, pp. 178\u2013183 (1989). https:\/\/doi.org\/10.1109\/SFCS.1989.63475","key":"14_CR27","DOI":"10.1109\/SFCS.1989.63475"},{"unstructured":"K\u00fcnnemann, M., Paturi, R., Schneider, S.: On the fine-grained complexity of one-dimensional dynamic programming. arXiv preprint arXiv:1703.00941 (2017)","key":"14_CR28"},{"doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Panolan, F., Ramanujan, M., Saurabh, S.: Lossy kernelization. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 224\u2013237 (2017)","key":"14_CR29","DOI":"10.1145\/3055399.3055456"},{"unstructured":"Manurangsi, P., Trevisan, L.: Mildly exponential time approximation algorithms for vertex cover, uniform sparsest cut and related problems. arXiv preprint arXiv:1807.09898 (2018)","key":"14_CR30"},{"doi-asserted-by":"crossref","unstructured":"Mucha, M., W\u0119grzycki, K., W\u0142odarczyk, M.: A subquadratic approximation scheme for partition. In: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 70\u201388. SIAM (2019)","key":"14_CR31","DOI":"10.1137\/1.9781611975482.5"},{"key":"14_CR32","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/BF01586040","volume":"54","author":"JB Orlin","year":"1992","unstructured":"Orlin, J.B., Ahuja, R.K.: New scaling algorithms for the assignment and minimum mean cycle problems. Math. Program. 54, 41\u201356 (1992). https:\/\/doi.org\/10.1007\/BF01586040","journal-title":"Math. Program."},{"issue":"1","key":"14_CR33","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/S0167-6377(02)00185-2","volume":"31","author":"T Polzin","year":"2003","unstructured":"Polzin, T., Daneshmand, S.V.: On Steiner trees and minimum spanning trees in hypergraphs. Oper. Res. Lett. 31(1), 12\u201320 (2003). https:\/\/doi.org\/10.1016\/S0167-6377(02)00185-2","journal-title":"Oper. Res. Lett."},{"key":"14_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1007\/978-3-540-79228-4_43","volume-title":"Theory and Applications of Models of Computation","author":"O Ponta","year":"2008","unstructured":"Ponta, O., H\u00fcffner, F., Niedermeier, R.: Speeding up dynamic programming for some NP-hard graph recoloring problems. In: Agrawal, M., Du, D., Duan, Z., Li, A. (eds.) TAMC 2008. LNCS, vol. 4978, pp. 490\u2013501. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-79228-4_43"},{"key":"14_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1007\/978-3-642-29627-7_22","volume-title":"Research in Computational Molecular Biology","author":"I Rauf","year":"2012","unstructured":"Rauf, I., Rasche, F., Nicolas, F., B\u00f6cker, S.: Finding maximum colorful subtrees in practice. In: Chor, B. (ed.) RECOMB 2012. LNCS, vol. 7262, pp. 213\u2013223. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-29627-7_22"},{"issue":"2","key":"14_CR36","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1089\/cmb.2006.13.133","volume":"13","author":"J Scott","year":"2006","unstructured":"Scott, J., Ideker, T., Karp, R.M., Sharan, R.: Efficient algorithms for detecting signaling pathways in protein interaction networks. J. Comput. Biol. 13(2), 133\u2013144 (2006)","journal-title":"J. Comput. Biol."},{"unstructured":"Shapira, A., Yuster, R., Zwick, U.: All-pairs bottleneck paths in vertex weighted graphs. In: SODA, vol.\u00a07, pp. 978\u2013985 (2007)","key":"14_CR37"},{"issue":"1","key":"14_CR38","doi-asserted-by":"publisher","first-page":"173","DOI":"10.4086\/toc.2009.v005a009","volume":"5","author":"V Vassilevska","year":"2009","unstructured":"Vassilevska, V., Williams, R.R., Yuster, R.: All pairs bottleneck paths and max-min matrix products in truly subcubic time. Theor. Comput. 5(1), 173\u2013189 (2009)","journal-title":"Theor. Comput."},{"unstructured":"Warme, D.M.: Spanning Trees in Hypergraphs with Applications to Steiner Trees. Ph.D. thesis, USA (1998). aAI9840474","key":"14_CR39"},{"unstructured":"W\u0119grzycki, K.: Provably Optimal Dynamic Programming (2019)","key":"14_CR40"},{"doi-asserted-by":"crossref","unstructured":"Williams, R.: Faster all-pairs shortest paths via circuit complexity. In: Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, pp. 664\u2013673 (2014)","key":"14_CR41","DOI":"10.1145\/2591796.2591811"},{"issue":"3","key":"14_CR42","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1145\/567112.567114","volume":"49","author":"U Zwick","year":"2002","unstructured":"Zwick, U.: All pairs shortest paths using bridging sets and rectangular matrix multiplication. J. ACM 49(3), 289\u2013317 (2002). https:\/\/doi.org\/10.1145\/567112.567114","journal-title":"J. ACM"}],"container-title":["Lecture Notes in Computer Science","Approximation and Online Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-81396-2_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,11]],"date-time":"2025-02-11T23:14:28Z","timestamp":1739315668000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-81396-2_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031813955","9783031813962"],"references-count":42,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-81396-2_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"12 February 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WAOA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Approximation and Online Algorithms","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Egham","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"United Kingdom","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"4 September 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"5 September 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"waoa2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/algo-conference.org\/2024\/waoa\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}