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

Optimizing sparsity over lattices and semigroups

Aliev, Iskander, Averkov, Gennadiy, De Lora, Jesus A. and Oertel, Timm 2020. Optimizing sparsity over lattices and semigroups. Lecture Notes in Computer Science

[img]
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: 31 Aug 2020 15:27
URI: http://orca.cf.ac.uk/id/eprint/130131

Citation Data

Cited 1 time 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