The Hungarian Algorithm with a Single Input Set

Let and be two finite sets of points with total cardinality . The maximum-cost many-to-many matching is a matching that matches each point in to ܣ at least o ܤ ne point in and each point in to at least one point in ݊ , such that sum of the matching costs is maximized. T ܣ he maximum-cost ma ܤ ny-to-many matchin ܤ g can be reduced t ܣ o the maximum-weight bipartite edge cover problem, and be solved in time using the Hungarian method. In the Hungarian algorithm it is assumed ଷ that the two sets and are disjoint. In this paper, we change the basic O H ሺn un ሻ garian algorithm, such that it can find the maximum-cost many-to-many matching between th ܣ e point ܤ s of a single set. We also present an algorithm for computing the degree satisfier maximum-cost many-to-many matching between and sets, where the degree demands of and are satisfied.

That is the points of and must be matched with at least and points of the other set, respectively. ܤ ܣ ܤ ܣ ܤ ܣ Keywords: many-to-many point D m ୅ atchin D g, ୆ Hungarian method, maximum-cost matching, single set, degree demand. 1. Introduction Let and be two finite sets of points with total cardinality . We can define a relationship between the points in and the points in using the concept of matc A hing. Th B is concept has various applications in computational n biology [1], A B 28 Fatemeh Rajabi Alni and Alireza Bagheri operations research [2], pattern recognition [3], computer vision [6], music information retrieval [8] and computational music theory [9]. A matching between two sets is a function that pairs individual points in one set with individual points in the other set. There are different types of matching. A one-to-one matching between and is a perfect matching between the two sets [7]. A many-to-one matching maps each point of to exactly one point of and each point of to at le A ast one B point of [5]. A one-to-many matching maps each point of to at least one point of and ea ܤ ܣ ch point of to exactly one point of [5]. A ܤ many-to-many matching b ܣ etween the two sets maps each point of to at leas A t one point of and vice-v B ersa [2]. A A B B Eiter and Mannila [10] have been originally studied the many-to-many matching problem as link distance. The link distance between two sets, is the minimum-cost many-to-many matching between the two...

Website: m-hikari.com | Filesize: -
No of Page(s): 9
Download The Hungarian Algorithm with a Single Input Set.pdf