{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T10:25:21Z","timestamp":1776767121787,"version":"3.51.2"},"reference-count":20,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":8350,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1983,12]]},"abstract":"Abstract<\/jats:title>This paper presents and solves in polynomial time the dynamic matching problem, an integer programming problem which involves matchings in a time\u2010expanded infinite network. The initial model is a finite directed graph G<\/jats:italic> = (V, E<\/jats:italic>) in which each edge has an associated real\u2010valued weight and an integral distance. We wish to \u201cmatch\u201d vertices over an infinite horizon, and we permit vertex i<\/jats:italic> in period p<\/jats:italic> to be matched to vertex j<\/jats:italic> in period r<\/jats:italic> if and only if there is an edge e<\/jats:italic> = (i, j<\/jats:italic>) of E<\/jats:italic> with distance r\u2010p<\/jats:italic> or else an edge e<\/jats:italic> = (j, i<\/jats:italic>) of E<\/jats:italic> with distance p\u2010r.<\/jats:italic> Equivalently, we construct a \u201cdynamic graph\u201d in which there is an edge incident to vertex i\u2010p<\/jats:italic> and to vertex j\u2010r<\/jats:italic> in the above cases. The weight of this matched edge in the dynamic (time\u2010expanded) graph is the weight of e.<\/jats:italic> The dynamic matching problem is to determine a matching M<\/jats:italic> in the dynamic graph such that M<\/jats:italic> has a maximum long\u2010run average weight per period. We show that the infinite horizon dynamic matching problem is linearly transformable to the finite horizon Q<\/jats:italic>\u2010matching problem, which is shown to be solvable in polynomial time in Part II of this paper.<\/jats:p>","DOI":"10.1002\/net.3230130407","type":"journal-article","created":{"date-parts":[[2007,5,11]],"date-time":"2007-05-11T17:18:03Z","timestamp":1178903883000},"page":"551-562","source":"Crossref","is-referenced-by-count":4,"title":["Dynamic matchings and quasidynamic fractional matchings. I"],"prefix":"10.1002","volume":"13","author":[{"given":"James B.","family":"Orlin","sequence":"first","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(80)90002-3"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0121194"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1965-045-4"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.6028\/jres.069B.013"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1975.5"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.6.3.419"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/321941.321942"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1307\/mmj\/1028998140"},{"key":"e_1_2_1_10_2","volume-title":"Computers and Intractibility: A Guide to the Theory of NP\u2010Completeness","author":"Garey M. R.","year":"1979"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230090204"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.28.1.106"},{"key":"e_1_2_1_13_2","volume-title":"Combinatorial Optimization: Networks and Matroids","author":"Lawler E. L.","year":"1976"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.21.2.517"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800260401"},{"key":"e_1_2_1_16_2","article-title":"Minimum convex cost dynamic network flows","author":"Orlin J.","journal-title":"Math. Oper. Res."},{"key":"e_1_2_1_17_2","doi-asserted-by":"crossref","unstructured":"J.Orlin The complexity of dynamic languages and dynamic optimization problems. In13th Annual Symposium on the Theory of Computing(1981)218\u2013227.","DOI":"10.1145\/800076.802475"},{"key":"e_1_2_1_18_2","doi-asserted-by":"crossref","unstructured":"J.Orlin 1982. Dynamic matchings and quasidynamic fractional matchings. II.Networks 13(1983)563\u2013580Part II of this series.","DOI":"10.1002\/net.3230130408"},{"key":"e_1_2_1_19_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230020304"},{"key":"e_1_2_1_20_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.19.7.1602"},{"key":"e_1_2_1_21_2","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800200311"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230130407","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230130407","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,20]],"date-time":"2023-10-20T02:59:30Z","timestamp":1697770770000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230130407"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1983,12]]},"references-count":20,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1983,12]]}},"alternative-id":["10.1002\/net.3230130407"],"URL":"https:\/\/doi.org\/10.1002\/net.3230130407","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1983,12]]}}}