Optimizing Sparsity over Lattices and Semigroups
Lists
Only you see this
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 \(\ell _0\)-norm. Our main results are improved bounds on the \(\ell _0\)-norm of sparse solutions to systems \(A\varvec{x}=\varvec{b}\), where \(A\in \mathbb {Z}^{m\times n}\), \({\varvec{b}}\in \mathbb {Z}^m\) and \(\varvec{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 \(\ell _0\)-norm satisfying the obtained bounds.
BibTeX
@inproceedings{aliev2020optimizing,
author = {Iskander Aliev and Gennadiy Averkov and Jesús A. De Loera and Timm Oertel},
title = {{Optimizing Sparsity over Lattices and Semigroups}},
booktitle = {IPCO},
year = {2020},
doi = {10.1007/978-3-030-45771-6\_4},
}| An algebraic perspective on integer sparse recovery | Appl. Math. Comput · 2019 |
| Sidon Sets of Fixed Cardinality and Lattice-Packings of Simplices | arXiv · 2016 |
| Integer Programming with GCD Constraints | arXiv · 2023 |
| On the maximal number of columns of a Δ-modular integer matrix: bounds and computations | Math. Program · 2024 |
| A discrete Farkas lemma | arXiv · 2003 |
| Certificates and relaxations for integer programming and the semi-group membership problem | arXiv · 2009 |