Minimum Many-to-Many Matchings for Computing the Distance Between Two Sequences

Mustafa Mohamad, David Rappaport, Godfried Toussaint

Research output: Contribution to journalArticle

Abstract

Motivated by a problem in music theory of measuring the distance between chords, scales, and rhythms we consider algorithms for obtaining a minimum-weight many-to-many matching between two sets of points on the real line. Given sets A and B, we seek to find the best rigid translation of B and a many-to-many matching that minimizes the sum of the squares of the distances between matched points. We provide discrete algorithms that solve this continuous optimization problem, and discuss other related matters.

Original languageEnglish (US)
Pages (from-to)1637-1648
Number of pages12
JournalGraphs and Combinatorics
Volume31
Issue number5
DOIs
StatePublished - Sep 24 2015

Keywords

  • Bipartite graph
  • Dynamic Programming
  • Many-to-many matching
  • Music Theory

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'Minimum Many-to-Many Matchings for Computing the Distance Between Two Sequences'. Together they form a unique fingerprint.

  • Cite this