# One-dimensional packing problem: Optimal decomposition of music structure

I am currently working on my Master thesis on the visualization of music structure and I'm looking to find an optimal description of repetitions found in a piece of music.

## Problem Description

Given a section range in a song in seconds (or samples) , e.g. [10,20], I can look up where this section is repeated. Then we end up with a set of repeating sections like: [[10,20], [40,50], [70,80]]. We call this a group. A group has a certain fitness given to it.

(As a sidenote, the fitness of a group is defined as a combination of the sum of similarity values and how much of the song they cover alltogether)

Our goal is to find a set of disjoint groups that altogether have the highest fitness; the optimal decomposition of the repetitions. Below are two different valid decompositions of the same song, one course, and one fine decomposition.

We are provided with a set of all candidate groups, here's a small selection, sorted top to bottom by fitness:

## Current Greedy Method

1. Sort all candidates by fitness
2. Pick group G with the highest fitness
3. Remove any groups from candidates if they have overlap with G
4. Repeat from step 2 until no candidates are left

## Bonus

Sometimes the candidates overlap every so slightly, which in the context should perhaps not immediately lead to disqualification.

There are options to relax the no-overlap rule. Note that each of the sections in a group has a different brightness. This brightness corresponds to a confidence, so in a group some sections are more certain to be proper repetitions than others.

For a group of sections G that we wish to add to a set of groups of sections S, we can:

• simply remove sections from G if they overlap with any sections in S
• trim the sides of to-be-added sections from G if they overlap with any sections in S
• keep the overlapping sections in G

I hope this problem is interesting enough to you to give it a shot! Thank you!

## 1 Answer

If $$n'$$ is the number of groups, this problem admits no $$2^{o(n')}$$-time algorithm for any choice of a constant $$\epsilon > 0$$, unless the exponential time hypothesis (ETH) fails.

Let $$G = (V, E)$$ be an undirected graph with $$n$$ vertices $$v_1, \dots, v_n$$ and $$m$$ edges $$e_1, \dots, e_m$$.

Construct an instance of your problem by creating $$n'=n$$ groups as follows:

• For each vertex $$v_i \in V$$, add a new group with fitness $$1$$ containing all intervals $$[j-1, j]$$ where $$j$$ is such that $$v_i$$ is an endpoint of $$e_j$$.

Any independent set $$S \subseteq V$$ of $$G$$ induces of collection of non-intersecting groups (except for the boundaries of the intervals) with total fitness $$|S|$$. On the converse, any subset of $$S'$$ non-intersecting groups must have total fitness $$|S'|$$ and induces an independent set of size $$|S'|$$ in $$G$$.

The claim follows since, assuming the ETH, there exists no $$2^{o(n)}$$-time algorithm for independent set.

Moreover, assuming $$\mathsf{P} \neq \mathsf{NP}$$, the above reduction also shows that for any constant $$\epsilon>0$$ there exists no polynomial-time $$n^{1-\epsilon}$$-approximation algorithm for your problem, even in the special case of unitary fitness. See, e.g., here.

• In your construction, two groups intersect if there is a path of length 2 in $G$ between the two vertices. To fix this, you can associate vertex $v_i$ with a list $[j-1,j]$ for all edges $e_j$ incident to $i$. Jan 15, 2021 at 15:34
• Thanks! I just added the interval $[i-1, i]$ in the group of $v_i$. This should fix it. Jan 15, 2021 at 15:42
• If $(i,j),(j,k) \in E$ then $[j-1,j]$ would appear both in the group of $v_i$ and in the group of $v_k$. Jan 15, 2021 at 15:44
• D'oh! I see it now... thanks. Jan 15, 2021 at 15:46
• Sorry, the $0$ was a typo. It should be $1$. Yes, in my reduction each interval is shared by exactly 2 groups. If each group is a set of integers noting changes: just le the group of $v_i$ be $\{j : v \mbox{ is an endpoint of } e_j\}$. Jan 15, 2021 at 16:42