Cardiff University | Prifysgol Caerdydd ORCA
Online Research @ Cardiff 
WelshClear Cookie - decide language by browser settings

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

[thumbnail of IPCO_sparse_solutions_revision.pdf]
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 Edit Item

Downloads

Downloads per month over past year

View more statistics