Reasoning about RoboCup soccer narratives
Hannaneh Hajishirzi, Julia Hockenmaier, et al.
UAI 2011
We describe a new heuristic for constructing a minimum-cost perfect matching designed for problems on complete graphs whose cost functions satisfy the triangle inequality (e.g., Euclidean problems). The running time for an n node problem is O(n log n) after a minimum-cost spanning tree is constructed. We also describe a procedure which, added to Kruskal's algorithm, produces a lower bound on the size of any perfect matching. This bound is based on a dual problem which has the following geometric interpretation for Euclidean problems: Pack nonoverlapping disks centered at the nodes and moats surrounding odd sets of nodes so as to maximize the sum of the disk radii and moat widths. © 1995 Springer-Verlag New York Inc.
Hannaneh Hajishirzi, Julia Hockenmaier, et al.
UAI 2011
Tong Zhang, G.H. Golub, et al.
Linear Algebra and Its Applications
Martin Charles Golumbic, Renu C. Laskar
Discrete Applied Mathematics
F.M. Schellenberg, M. Levenson, et al.
BACUS Symposium on Photomask Technology and Management 1991