Optimizing sparsity over lattices and semigroups

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