Aliev, Iskander ORCID: https://orcid.org/0000-0002-2206-9207, Averkov, Gennadiy, De Lora, Jesus A. and Oertel, Timm ORCID: https://orcid.org/0000-0001-5720-8978 2020. Optimizing sparsity over lattices and semigroups. Lecture Notes in Computer Science |
Preview |
PDF
- Accepted Post-Print Version
Available under License Creative Commons Attribution. Download (325kB) | Preview |
Abstract
Motivated by problems in optimization we study the sparsity of the solutions to systems of linear Diophantine equations and linear integer programs, i.e., the number of non-zero entries of a solution, which is often referred to as the ℓ0-norm. Our main results are improved bounds on the ℓ0-norm of sparse solutions to systems Ax=b, where A∈Zm×n, b∈Zm and x is either a general integer vector (lattice case) or a non-negative integer vector (semigroup case). In the lattice case and certain scenarios of the semigroup case, we give polynomial time algorithms for computing solutions with ℓ0-norm satisfying the obtained bounds.
Item Type: | Article |
---|---|
Schools: | Mathematics |
Publisher: | Springer Verlag |
ISSN: | 0302-9743 |
Date of First Compliant Deposit: | 5 March 2020 |
Date of Acceptance: | 29 February 2020 |
Last Modified: | 08 Nov 2023 13:01 |
URI: | https://orca.cardiff.ac.uk/id/eprint/130131 |
Citation Data
Cited 7 times in Scopus. View in Scopus. Powered By Scopus® Data
Actions (repository staff only)
Edit Item |