Aliev I, Averkov G, De Loera JA, Oertel T (2020)

**Publication Type:** Conference contribution

**Publication year:** 2020

**Publisher:** Springer

**Book Volume:** 12125 LNCS

**Pages Range:** 40-51

**Conference Proceedings Title:** Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

**ISBN:** 9783030457709

**DOI:** 10.1007/978-3-030-45771-6_4

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 [Formula Presented]-norm. Our main results are improved bounds on the [Formula Presented]-norm of sparse solutions to systems [Formula Presented], where [Formula Presented], [Formula Presented] and [Formula Presented] 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 [Formula Presented]-norm satisfying the obtained bounds.

Brandenburgische Technische Universität Cottbus-Senftenberg (BTU)
Germany (DE)
University of California Davis (UCDAVIS)
United States (USA) (US)
Cardiff University
United Kingdom (GB)

**APA:**

Aliev, I., Averkov, G., De Loera, J.A., & Oertel, T. (2020). Optimizing Sparsity over Lattices and Semigroups. In Daniel Bienstock, Giacomo Zambelli (Eds.), *Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)* (pp. 40-51). London, GB: Springer.

**MLA:**

Aliev, Iskander, et al. "Optimizing Sparsity over Lattices and Semigroups." *Proceedings of the 21st International Conference on Integer Programming and Combinatorial Optimization, IPCO 2020, London* Ed. Daniel Bienstock, Giacomo Zambelli, Springer, 2020. 40-51.

**BibTeX:** Download