{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,2]],"date-time":"2026-02-02T20:29:10Z","timestamp":1770064150409,"version":"3.49.0"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2022,3,23]],"date-time":"2022-03-23T00:00:00Z","timestamp":1647993600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,3,23]],"date-time":"2022-03-23T00:00:00Z","timestamp":1647993600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100016379","name":"Universit\u00e4t Osnabr\u00fcck","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100016379","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In <jats:italic>multistage perfect matching<\/jats:italic> problems, we are given a sequence of graphs on the same vertex set and are asked to find a sequence of perfect matchings, corresponding to the sequence of graphs, such that consecutive matchings are as similar as possible. More precisely, we aim to maximize the intersections, or minimize the unions between consecutive matchings. We show that these problems are NP-hard even in very restricted scenarios. As our main contribution, we present the first non-trivial approximation algorithms for these problems: On the one hand, we devise a tight approximation on graph sequences of length\u00a0two (2-stage graphs). On the other hand, we propose several general methods to deduce multistage approximations from blackbox approximations on 2-stage graphs.\n<\/jats:p>","DOI":"10.1007\/s00453-022-00951-x","type":"journal-article","created":{"date-parts":[[2022,3,23]],"date-time":"2022-03-23T06:02:47Z","timestamp":1648015367000},"page":"2135-2153","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Approximating Multistage Matching Problems"],"prefix":"10.1007","volume":"84","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4681-5550","authenticated-orcid":false,"given":"Markus","family":"Chimani","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7412-2770","authenticated-orcid":false,"given":"Niklas","family":"Troost","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5923-4114","authenticated-orcid":false,"given":"Tilo","family":"Wiedera","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,3,23]]},"reference":[{"key":"951_CR1","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1016\/j.jcss.2019.08.002","volume":"107","author":"EC Akrida","year":"2020","unstructured":"Akrida, E.C., Mertzios, G.B., Spirakis, P.G., Zamaraev, V.: Temporal vertex cover with a sliding time window. J. Comput. Syst. Sci. 107, 108\u2013123 (2020). https:\/\/doi.org\/10.1016\/j.jcss.2019.08.002","journal-title":"J. Comput. Syst. Sci."},{"key":"951_CR2","doi-asserted-by":"publisher","unstructured":"Bampis, E., Escoffier, B., Lampis, M., Paschos, V.T.: Multistage matchings. In: 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018), vol.\u00a0101, pp. 7:1\u20137:13 (2018). https:\/\/doi.org\/10.4230\/LIPIcs.SWAT.2018.7","DOI":"10.4230\/LIPIcs.SWAT.2018.7"},{"key":"951_CR3","doi-asserted-by":"publisher","unstructured":"Bampis, E., Escoffier, B., Schewior, K., Teiller, A.: Online multistage subset maximization problems. In: 27th Annual European Symposium on Algorithms (ESA 2019), vol.\u00a0144, pp. 11:1\u201311:14 (2019). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2019.11","DOI":"10.4230\/LIPIcs.ESA.2019.11"},{"key":"951_CR4","doi-asserted-by":"publisher","unstructured":"Bampis, E., Escoffier, B., Teiller, A.: Multistage knapsack. In: 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019), vol.\u00a0138, pp. 22:1\u201322:14 (2019). https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2019.22","DOI":"10.4230\/LIPIcs.MFCS.2019.22"},{"key":"951_CR5","doi-asserted-by":"publisher","unstructured":"Bampis, E., Escoffier, B., Kononov, A.V.: Lp-based algorithms for multistage minimization problems. In: Approximation and Online Algorithms: 18th International Workshop, WAOA 2020, Virtual Event, September 9\u201310, 2020, Revised Selected Papers, pp. 1\u201315 (2020). https:\/\/doi.org\/10.1007\/978-3-030-80879-2_1","DOI":"10.1007\/978-3-030-80879-2_1"},{"key":"951_CR6","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1016\/j.tcs.2019.03.026","volume":"806","author":"J Baste","year":"2020","unstructured":"Baste, J., Bui-Xuan, B.M., Roux, A.: Temporal matching. Theor. Comput. Sci. 806, 184\u2013196 (2020). https:\/\/doi.org\/10.1016\/j.tcs.2019.03.026","journal-title":"Theor. Comput. Sci."},{"key":"951_CR7","doi-asserted-by":"publisher","unstructured":"Bernstein, A., Stein, C.: Fully dynamic matching in bipartite graphs. In: Proceedings of 42nd International Colloquium on Automata, Languages and Programming (ICALP 2015), pp. 167\u2013179 (2015). https:\/\/doi.org\/10.1007\/978-3-662-47672-7_14","DOI":"10.1007\/978-3-662-47672-7_14"},{"issue":"3","key":"951_CR8","doi-asserted-by":"publisher","first-page":"859","DOI":"10.1137\/140998925","volume":"47","author":"S Bhattacharya","year":"2018","unstructured":"Bhattacharya, S., Henzinger, M., Italiano, G.F.: Deterministic fully dynamic data structures for vertex cover and matching. SIAM J. Comput. 47(3), 859\u2013887 (2018). https:\/\/doi.org\/10.1137\/140998925","journal-title":"SIAM J. Comput."},{"key":"951_CR9","doi-asserted-by":"publisher","unstructured":"Bosek, B., Leniowski, D., Sankowski, P., Zych, A.: Online bipartite matching in offline time. In: 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pp. 384\u2013393 (2014). https:\/\/doi.org\/10.1109\/FOCS.2014.48","DOI":"10.1109\/FOCS.2014.48"},{"issue":"2","key":"951_CR10","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1017\/nws.2019.13","volume":"7","author":"R Bredereck","year":"2019","unstructured":"Bredereck, R., Komusiewicz, C., Kratsch, S., Molter, H., Niedermeier, R., Sorge, M.: Assessing the computational complexity of multilayer subgraph detection. Netw. Sci. 7(2), 215\u2013241 (2019). https:\/\/doi.org\/10.1017\/nws.2019.13","journal-title":"Netw. Sci."},{"key":"951_CR11","unstructured":"Casteigts, A.: A journey through dynamic networks (with excursions). Habilitation, Universit\u00e9 de Bordeaux (2018)"},{"key":"951_CR12","doi-asserted-by":"crossref","unstructured":"Chimani, M., Troost, N., Wiedera, T.: A general approach to approximate multistage subgraph problems. CoRR (2021). arXiv:2107.02581","DOI":"10.1007\/978-3-030-79987-8_39"},{"key":"951_CR13","doi-asserted-by":"publisher","unstructured":"Eppstein, D.: Offline algorithms for dynamic minimum spanning tree problems. In: Algorithms and Data Structures (WADS 1991), pp. 392\u2013399 (1991). https:\/\/doi.org\/10.1007\/BFb0028278","DOI":"10.1007\/BFb0028278"},{"key":"951_CR14","doi-asserted-by":"publisher","unstructured":"Fluschnik, T., Niedermeier, R., Rohm, V., Zschoche, P.: Multistage vertex cover. In: 14th International Symposium on Parameterized and Exact Computation (IPEC 2019), vol.\u00a0148, pp. 14:1\u201314:14 (2019). https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2019.14","DOI":"10.4230\/LIPIcs.IPEC.2019.14"},{"key":"951_CR15","unstructured":"Garey, M.R., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H Freeman (1979)"},{"key":"951_CR16","doi-asserted-by":"publisher","unstructured":"Gupta, A., Talwar, K., Wieder, U.: Changing bases: multistage optimization for matroids and matchings. In: Proceedings of 41st International Colloquium on Automata, Languages and Programming (ICALP 2014) (2014). https:\/\/doi.org\/10.1007\/978-3-662-43948-7_47","DOI":"10.1007\/978-3-662-43948-7_47"},{"key":"951_CR17","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1016\/j.tcs.2021.04.002","volume":"868","author":"K Heeger","year":"2021","unstructured":"Heeger, K., Himmel, A.S., Kammer, F., Niedermeier, R., Renken, M., Sajenko, A.: Multistage problems on a global budget. Theor. Comput. Sci. 868, 46\u201364 (2021). https:\/\/doi.org\/10.1016\/j.tcs.2021.04.002","journal-title":"Theor. Comput. Sci."},{"key":"951_CR18","doi-asserted-by":"publisher","unstructured":"Kempe, D., Kleinberg, J.M., Kumar, A.: Connectivity and inference problems for temporal networks. In: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing (STOC 2000), pp. 504\u2013513 (2000). https:\/\/doi.org\/10.1145\/335305.335364","DOI":"10.1145\/335305.335364"},{"key":"951_CR19","unstructured":"Lov\u00e1sz, L., Plummer, M.: Matching Theory, American Mathematical Society (1986)"},{"key":"951_CR20","doi-asserted-by":"publisher","unstructured":"Mertzios, G.B., Molter, H., Niedermeier, R., Zamaraev, V., Zschoche, P.: Computing maximum matchings in temporal graphs. In: 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020), pp. 27:1\u201327:14 (2020). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2020.27","DOI":"10.4230\/LIPIcs.STACS.2020.27"},{"key":"951_CR21","doi-asserted-by":"publisher","unstructured":"Michail, O., Spirakis, P.G.: Traveling salesman problems in temporal graphs. In: Mathematical Foundations of Computer Science 2014 (MFCS 2014) (2014). https:\/\/doi.org\/10.1007\/978-3-662-44465-8_47","DOI":"10.1007\/978-3-662-44465-8_47"},{"key":"951_CR22","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(89)90005-9","author":"MO Rabin","year":"1989","unstructured":"Rabin, M.O., Vazirani, V.V.: Maximum matchings in general graphs through randomization. J. Algorithms (1989). https:\/\/doi.org\/10.1016\/0196-6774(89)90005-9","journal-title":"J. Algorithms"},{"key":"951_CR23","unstructured":"Sankowski, P.: Faster dynamic matchings and vertex connectivity. In: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), pp. 118\u2013126 (2007)"},{"key":"951_CR24","doi-asserted-by":"publisher","unstructured":"Thorup, M.: Near-optimal fully-dynamic graph connectivity. In: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing (STOC 2000), pp. 343\u2013350 (2000). https:\/\/doi.org\/10.1145\/335305.335345","DOI":"10.1145\/335305.335345"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00951-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-00951-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00951-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,27]],"date-time":"2022-09-27T05:05:48Z","timestamp":1664255148000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-00951-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,23]]},"references-count":24,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2022,8]]}},"alternative-id":["951"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-00951-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,3,23]]},"assertion":[{"value":"31 August 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 February 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 March 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}