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

Mustafa Mohamad; David Rappaport; Godfried Toussaint

doi:10.1007/s00373-014-1467-4

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

Mustafa Mohamad, David Rappaport, Godfried Toussaint

Computer Science

Research output: Contribution to journal › Article › peer-review

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 language	English (US)
Pages (from-to)	1637-1648
Number of pages	12
Journal	Graphs and Combinatorics
Volume	31
Issue number	5
DOIs	https://doi.org/10.1007/s00373-014-1467-4
State	Published - 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

Access to Document

10.1007/s00373-014-1467-4

Cite this

@article{04909d52d3604fecb60cae4aaf8faf24,

title = "Minimum Many-to-Many Matchings for Computing the Distance Between Two Sequences",

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.",

keywords = "Bipartite graph, Dynamic Programming, Many-to-many matching, Music Theory",

author = "Mustafa Mohamad and David Rappaport and Godfried Toussaint",

note = "Publisher Copyright: {\textcopyright} 2014, Springer Japan.",

year = "2015",

month = sep,

day = "24",

doi = "10.1007/s00373-014-1467-4",

language = "English (US)",

volume = "31",

pages = "1637--1648",

journal = "Graphs and Combinatorics",

issn = "0911-0119",

publisher = "Springer Japan",

number = "5",

}

TY - JOUR

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

AU - Mohamad, Mustafa

AU - Rappaport, David

AU - Toussaint, Godfried

PY - 2015/9/24

Y1 - 2015/9/24

N2 - 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.

AB - 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.

KW - Bipartite graph

KW - Dynamic Programming

KW - Many-to-many matching

KW - Music Theory

UR - http://www.scopus.com/inward/record.url?scp=84940436578&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84940436578&partnerID=8YFLogxK

U2 - 10.1007/s00373-014-1467-4

DO - 10.1007/s00373-014-1467-4

M3 - Article

AN - SCOPUS:84940436578

SN - 0911-0119

VL - 31

SP - 1637

EP - 1648

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

IS - 5

ER -

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

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this