### 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 | |

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

## 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

Mohamad, M., Rappaport, D., & Toussaint, G. (2015). Minimum Many-to-Many Matchings for Computing the Distance Between Two Sequences.

*Graphs and Combinatorics*,*31*(5), 1637-1648. https://doi.org/10.1007/s00373-014-1467-4