Dynamic matchings and quasidynamic fractional matchings. I

Publisher Website
Google Scholar
Abstract
This paper presents and solves in polynomial time the dynamic matching problem, an integer programming problem which involves matchings in a time‐expanded infinite network. The initial model is a finite directed graph G = (V, E) in which each edge has an associated real‐valued weight and an integral distance. We wish to “match” vertices over an infinite horizon, and we permit vertex i in period p to be matched to vertex j in period r if and only if there is an edge e = (i, j) of E with distance r‐p or else an edge e = (j, i) of E with distance p‐r. Equivalently, we construct a “dynamic graph” in which there is an edge incident to vertex i‐p and to vertex j‐r in the above cases. The weight of this matched edge in the dynamic (time‐expanded) graph is the weight of e. The dynamic matching problem is to determine a matching M in the dynamic graph such that M has a maximum long‐run average weight per period. We show that the infinite horizon dynamic matching problem is linearly transformable to the finite horizon Q‐matching problem, which is shown to be solvable in polynomial time in Part II of this paper.

This publication has 17 references indexed in Scilit: