Milan Hladík. Absolute value equations with 2n solutions. Optim. Lett., 20(3):559–575, April 2026.
[PDF] [gzipped postscript] [postscript] [HTML]
An absolute value equation system is an algebraic problem that involves solving the $n$-by-$n$ system $Ax+|x|=b$. This problem is known to be NP-hard, and its solution set can have a complicated structure. So far, the research has primarily focused on the unique solvability cases. However, the system can possess up to $2^n$ solutions, provided there are finitely many of them. In this paper, we completely characterize this case, analysing which matrices $A$ and vectors $b$ allow for this situation. We also examine the computational complexity of the problem and present novel sufficient conditions. Eventually, we provide remarks regarding possible extensions to the system of the form $Ax+B|x|=b$.
@article{Hla2026b,
author = "Milan Hlad\'{\i}k",
title = "Absolute value equations with $2^n$ solutions",
webtitle = "Absolute value equations with 2<sup>n</sup> solutions",
journal = "Optim. Lett.",
fjournal = "Optimization Letters",
volume = "20",
number = "3",
pages = "559-575",
month = "April",
year = "2026",
doi = "10.1007/s11590-025-02251-z",
issn = "1862-4480",
url = "https://link.springer.com/article/10.1007/s11590-025-02251-z",
bib2html_dl_html = "https://doi.org/10.1007/s11590-025-02251-z",
bib2html_dl_pdf = "https://rdcu.be/e9LY5",
abstract = "An absolute value equation system is an algebraic problem that involves solving the $n$-by-$n$ system $Ax+|x|=b$. This problem is known to be NP-hard, and its solution set can have a complicated structure. So far, the research has primarily focused on the unique solvability cases. However, the system can possess up to $2^n$ solutions, provided there are finitely many of them. In this paper, we completely characterize this case, analysing which matrices $A$ and vectors $b$ allow for this situation. We also examine the computational complexity of the problem and present novel sufficient conditions. Eventually, we provide remarks regarding possible extensions to the system of the form $Ax+B|x|=b$.",
keywords = "Absolute value equations; Multiple solutions; Computational complexity; Linear complementarity problem",
}
Generated by bib2html.pl (written by Patrick Riley ) on Thu Jul 02, 2026 12:34:40