Target-based computer-assisted orchestration: Complexity and approximation algorithms

Target-based computer-assisted orchestration can be thought of as the process of searching for combinations of orchestral sounds in a database of sound samples to match a given sound (called target) while respecting specific symbolic constraints (such as the musical instruments that we can use). It is modeled as a combinatorial optimization problem, where the feasible solutions are subsets of orchestral sounds, and the function to minimize measures a distance between the chosen subset of orchestral sounds and the target. In this article, we focus on this optimization problem and analyse it through the lens of computational complexity and approximation algorithms. We first study the so-called static case where there is no temporality in the target sound (we want to reproduce a ‘single’ constant sound). We show that the problem is already NP-hard, but is solvable by a pseudo-polynomial-time algorithm. We also provide an approximation algorithm with additive error. We then consider the more general case with temporality, when the target sound can be seen as a sequence of sounds over a time horizon. We show how the previous results in the static case generalize in this temporal case. We conclude our study with some experiments on real target sounds.