Optimizing Sparsity over Lattices and Semigroups
Aliev I, Averkov G, De Loera JA, Oertel T (2020)
Publication Type: Conference contribution
Publication year: 2020
Journal
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)
Event location: London
ISBN: 9783030457709
DOI: 10.1007/978-3-030-45771-6_4
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 [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.
Authors with CRIS profile
Involved external institutions
Brandenburgische Technische Universität Cottbus-Senftenberg (BTU)
Germany (DE)
University of California Davis (UCDAVIS)
United States (USA) (US)
Cardiff University
United Kingdom (GB)
Germany (DE)
University of California Davis (UCDAVIS)
United States (USA) (US)
Cardiff University
United Kingdom (GB)
How to cite
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