Learning Reduced Order Dynamics via Geometric Representations
Imran Nasim, Melanie Weber
SCML 2024
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.
Imran Nasim, Melanie Weber
SCML 2024
Sonia Cafieri, Jon Lee, et al.
Journal of Global Optimization
Jonathan Ashley, Brian Marcus, et al.
Ergodic Theory and Dynamical Systems
Vladimir Yanovski, Israel A. Wagner, et al.
Ann. Math. Artif. Intell.