Graph problems arising from parameter identification of discrete dynamical systems

Graph problems arising from parameter identification of discrete dynamical systems

0.00 Avg rating0 Votes
Article ID: iaor20116145
Volume: 73
Issue: 3
Start Page Number: 381
End Page Number: 400
Publication Date: Jun 2011
Journal: Mathematical Methods of Operations Research
Authors: , , , , ,
Keywords: combinatorial optimization
Abstract:

This paper focuses on combinatorial feasibility and optimization problems that arise in the context of parameter identification of discrete dynamical systems. Given a candidate parametric model for a physical system and a set of experimental observations, the objective of parameter identification is to provide estimates of the parameter values for which the model can reproduce the experiments. To this end, we define a finite graph corresponding to the model, to each arc of which a set of parameters is associated. Paths in this graph are regarded as feasible only if the sets of parameters corresponding to the arcs of the path have nonempty intersection. We study feasibility and optimization problems on such feasible paths, focusing on computational complexity. We show that, under certain restrictions on the sets of parameters, some of the problems become tractable, whereas others are NP‐hard. In a similar vein, we define and study some graph problems for experimental design, whose goal is to support the scientist in optimally designing new experiments.

Reviews

Required fields are marked *. Your email address will not be published.