Matching on a line
From MaRDI portal
Publication:6301016
arXiv1805.00214MaRDI QIDQ6301016FDOQ6301016
Authors: Josef Bukac 
Publication date: 1 May 2018
Abstract: Matching is a method of the design of experiments. If we had an even number of patients and wanted to form pairs of patients such that their ages, for example, in each pair be as close as possible, we would use nonbipartite matching. Not only do we present a fast method to do this, we also extend our approach to triples, quadruples, etc. In part 1 a matching algorithm uses kn points on a line as vertices, pairs of vertices as edges, and either absolute values of differences or the squares of differences as weights or distances. It forms n of k-tuples with the minimal sum of distances within each k-tuple in O(n log n) time. In part 2 we present a trivial algorithm for bipartite matching with absolute values or squares of differences as weights and a generalisation to tripartite matching on tripartite graphs.
Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
This page was built for publication: Matching on a line
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6301016)
