D-Optimal Data Fusion: Exact and Approximation Algorithms
From MaRDI portal
Publication:6202334
DOI10.1287/IJOC.2022.0235arXiv2208.03589MaRDI QIDQ6202334FDOQ6202334
Authors: Marcia Fampa, Jon Lee, Feng Qiu, Weijun Xie, Rui Yao 
Publication date: 26 March 2024
Published in: INFORMS Journal on Computing (Search for Journal in Brave)
Abstract: We study the D-optimal Data Fusion (DDF) problem, which aims to select new data points, given an existing Fisher information matrix, so as to maximize the logarithm of the determinant of the overall Fisher information matrix. We show that the DDF problem is NP-hard and has no constant-factor polynomial-time approximation algorithm unless P NP. Therefore, to solve the DDF problem effectively, we propose two convex integer-programming formulations and investigate their corresponding complementary and Lagrangian-dual problems. We also develop scalable randomized-sampling and local-search algorithms with provable performance guarantees. Leveraging the concavity of the objective functions in the two proposed formulations, we design an exact algorithm, aimed at solving the DDF problem to optimality. We further derive a family of submodular valid inequalities and optimality cuts, which can significantly enhance the algorithm performance. Finally, we test our algorithms using real-world data on the new phasor-measurement-units placement problem for modern power grids, considering the existing conventional sensors. Our numerical study demonstrates the efficiency of our exact algorithm and the scalability and high-quality outputs of our approximation algorithms.
Full work available at URL: https://arxiv.org/abs/2208.03589
D-optimalitydata fusionapproximation algorithmFisher information matrixexact algorithmmaximum-entropy samplingoptimality cutsubmodular inequality
This page was built for publication: D-Optimal Data Fusion: Exact and Approximation Algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6202334)
