.png){kind=icon}
.png){kind=icon}
Return
Target-based computer-assisted orchestration: Complexity and approximation algorithms
.png){kind=icon}
PRE
AI
DOI：10.1016/j.ejor.2022.05.008.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Target-based computer-assisted orchestration can be thought of as the process of searching for combina-tions 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 com-putational 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 tempo-rality, 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.(c) 2022 Elsevier B.V. All rights reserved.
Keywords:
Complexity theory
Multistage optimization
Approximation algorithms
Automated orchestration
Journal
IF:
6
Papers:
2.2W
Citations:
6.4W