Milan Hladík, Michal Černý, and Vladik Kreinovich. Optimization of quadratic forms and t-norm forms on interval domain and computational complexity. In S. N. Shahbazova and others, editors, Recent Developments and the New Direction in Soft-Computing Foundations and Applications, STUDFUZZ, pp. 101–108, Springer, Cham, 2021.
[PDF] [gzipped postscript] [postscript] [HTML]
We consider the problem of maximization of a quadratic form over a box. We identify the NP-hardness boundary for sparse quadratic forms: the problem is polynomially solvable for $O(łog(n))$ nonzero entries, but it is NP-hard if the number of nonzero entries is of the order $n^\varepsilon$ for an arbitrarily small $\varepsilon>0$. Then we inspect further polynomially solvable cases. We define a sunflower graph over the quadratic form and study efficiently solvable cases according to the shape of this graph (e.g. the case with small sunflower leaves or the case with a restricted number of negative entries). Finally, we define a generalized quadratic form, called t-norm form, where the quadratic terms are replaced by t-norms. We prove that the optimization problem remains NP-hard with an arbitrary Lipschitz continuous t-norm.
@inCollection{HlaCer2021b,
author = "Milan Hlad\'{\i}k and Michal {\v{C}}ern\'{y} and Vladik Kreinovich",
title = "Optimization of quadratic forms and t-norm forms on interval domain and computational complexity",
editor = "S. N. Shahbazova and others",
feditor = "Shahbazova, Shahnaz N. and Kacprzyk, Janusz and Balas, Valentina Emilia and Kreinovich, Vladik",
booktitle = "Recent Developments and the New Direction in Soft-Computing Foundations and Applications",
fbooktitle = "Recent Developments and the New Direction in Soft-Computing Foundations and Applications: Selected Papers from the 7th World Conference on Soft Computing, May 29--31, 2018, Baku, Azerbaijan",
publisher = "Springer",
address = "Cham",
series = "STUDFUZZ",
fseries = "Studies in Fuzziness and Soft Computing",
volume = "393",
pages = "101-108",
year = "2021",
doi = "10.1007/978-3-030-47124-8_9",
isbn = "978-3-030-47124-8",
url = "https://doi.org/10.1007/978-3-030-47124-8_9",
bib2html_dl_html = "https://link.springer.com/chapter/10.1007/978-3-030-47124-8_9",
abstract = "We consider the problem of maximization of a quadratic form over a box. We identify the NP-hardness boundary for sparse quadratic forms: the problem is polynomially solvable for $O(\log(n))$ nonzero entries, but it is NP-hard if the number of nonzero entries is of the order $n^{\varepsilon}$ for an arbitrarily small $\varepsilon>0$. Then we inspect further polynomially solvable cases. We define a sunflower graph over the quadratic form and study efficiently solvable cases according to the shape of this graph (e.g. the case with small sunflower leaves or the case with a restricted number of negative entries). Finally, we define a generalized quadratic form, called t-norm form, where the quadratic terms are replaced by t-norms. We prove that the optimization problem remains NP-hard with an arbitrary Lipschitz continuous t-norm.",
keywords = "Interval computation; NP-hardness; Quadratic form; t-form",
}
Generated by bib2html.pl (written by Patrick Riley ) on Wed Oct 23, 2024 08:16:44