home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / sci / math / 10437 < prev    next >
Encoding:
Internet Message Format  |  1992-08-20  |  2.3 KB
  1. Path: sparky!uunet!munnari.oz.au!yoyo.aarnet.edu.au!sirius.ucs.adelaide.edu.au!levels!8321207d
  2. From: 8321207d@levels.unisa.edu.au
  3. Newsgroups: sci.math
  4. Subject: Matching algorithm
  5. Message-ID: <18353.2a93ce73@levels.unisa.edu.au>
  6. Date: 20 Aug 92 07:25:15 GMT
  7. Organization: University of South Australia
  8. Lines: 44
  9.  
  10.  
  11. Hello folks, this is a first for me.
  12.  
  13. Can anyone help with the following (sorry for being verbose).
  14.  
  15. Suppose you have a number of choirs with different numbers of people in
  16. each. The voice ranges of the choir members are known. It is possible
  17. that the ranges of some of the people overlap; for example, person A may
  18. sing in the range 2000-2500 Hz while person B sings in the range 2300-
  19. 2650 Hz. Furthermore, some of the people in a particular choir may have 
  20. other links between them, for instance person C could sing one octave
  21. (whatever an octave is) higher than person A.
  22.  
  23. Suppose now that one of the choirs performed and this performance was
  24. recorded. If the recording of the performance is analyzed then it is
  25. possible to isolated various bands within which singing took place.
  26.  
  27. The problem is to identify which choir was singing. However, care must
  28. be exercised during this process because when a particular voice band
  29. gets associated with a paerson in a choir, then there are consequences
  30. due to possible links which may exist between the people. Hence associating
  31. a voice band of 2350-2450 Hz with person A may result in the singing
  32. range for person D being restricted to a new range if person D sings
  33. at say 1.5 times that of person A. This may mean that no voice band can
  34. subsequently be matched with person D based on the initial match of
  35. person A.
  36.  
  37. A scoring function for the quality of the match exist and the objective
  38. is to maximise the score. It has been suggested to me that this falls
  39. in the category of being a matching problem as found in Graph Theory.
  40. A check through available literature had matching problems which did
  41. not make use of additional constraining information.
  42.  
  43. My query is whether a matching algorithm which makes use of side
  44. constraints exists and if so what are some pointers to it?
  45. Also could this be solved (or a valiant attempt made at doing so)
  46. by some other scheme aside from exhaustively considering every possible
  47. pairing between person and voice band?
  48.  
  49. Any information gratefully accepted.
  50. Contact via email or post
  51.  
  52. Cheers
  53. Paul
  54.