NetNews Usenet Archive 1992 #18/NN_1992_18.iso/spool/sci/math/10459

Text File | 1992-08-20 | 3.6 KB | 81 lines

Newsgroups: sci.math
Path: sparky!uunet!destroyer!ubc-cs!unixg.ubc.ca!unixg.ubc.ca!israel
From: [e-mail] (Robert B. Israel)
Subject: Re: Matching algorithm
Message-ID: <[e-mail]>
Sender: [e-mail] (Usenet News Maintenance)
Nntp-Posting-Host: unixg.ubc.ca
Organization: University of British Columbia, Vancouver, B.C., Canada
References: <[e-mail]>
Date: Thu, 20 Aug 1992 20:15:02 GMT
Lines: 68

In <[e-mail]> [e-mail] writes:


>Hello folks, this is a first for me.

>Can anyone help with the following (sorry for being verbose).

>Suppose you have a number of choirs with different numbers of people in
>each. The voice ranges of the choir members are known. It is possible
>that the ranges of some of the people overlap; for example, person A may
>sing in the range 2000-2500 Hz while person B sings in the range 2300-
>2650 Hz. Furthermore, some of the people in a particular choir may have
>other links between them, for instance person C could sing one octave
>(whatever an octave is) higher than person A.

>Suppose now that one of the choirs performed and this performance was
>recorded. If the recording of the performance is analyzed then it is
>possible to isolated various bands within which singing took place.

>The problem is to identify which choir was singing. However, care must
>be exercised during this process because when a particular voice band
>gets associated with a paerson in a choir, then there are consequences
>due to possible links which may exist between the people. Hence associating
>a voice band of 2350-2450 Hz with person A may result in the singing
>range for person D being restricted to a new range if person D sings
>at say 1.5 times that of person A. This may mean that no voice band can
>subsequently be matched with person D based on the initial match of
>person A.

>A scoring function for the quality of the match exist and the objective
>is to maximise the score. It has been suggested to me that this falls
>in the category of being a matching problem as found in Graph Theory.
>A check through available literature had matching problems which did
>not make use of additional constraining information.

>My query is whether a matching algorithm which makes use of side
>constraints exists and if so what are some pointers to it?
>Also could this be solved (or a valiant attempt made at doing so)
>by some other scheme aside from exhaustively considering every possible
>pairing between person and voice band?

Since you're matching one type of thing (voice bands) to another (people),
your graph is bipartite, and you have an "assignment problem" rather than
a "matching problem".  (This is good, because algorithms for assignment
and other network-flow problems are easier and more readily available
than for matching problems)

If I understand your question, the "side conditions" are of the type
"match band 1 to person A if you match band 2 to person B".  This takes
you out of the realm of network flows.  But you still can treat it as
a linear programming problem.  The catch is that the linear programming
problem may have non-integer optimal solutions.  If you happen to get a
solution in integers (which is not all that unlikely if there are not
too many of these side conditions), then you've solved your problem.
Otherwise, you have to go to integer programming.

Hope this helps.

>Any information gratefully accepted.
>Contact via email or post

>Cheers
>Paul
--
Robert Israel                            [e-mail]
Department of Mathematics             or [e-mail]
University of British Columbia
Vancouver, BC, Canada V6T 1Y4