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

Evripidis Bampis, Carmine-Emanuele Cella, Bruno Escoffier, Mila Rocco and Alexandre Teiller

European Journal of Operational Research, 2023, vol. 304, issue 3, 926-938

Abstract: 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.

Keywords: Complexity theory; Multistage optimization; Approximation algorithms; Automated orchestration (search for similar items in EconPapers)
Date: 2023
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221722003678
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:304:y:2023:i:3:p:926-938

DOI: 10.1016/j.ejor.2022.05.008

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().