Sparse approximation in lattices and semigroups

• 成果类型: Article; Early Access
• 署名作者: Kuhlmann, Stefan; Oertel, Timm; Weismantel, Robert
• 署名单位: Swiss Federal Institutes of Technology Domain; ETH Zurich; University of Erlangen Nuremberg
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610; 1436-4646
• DOI: 10.1007/s10107-026-02340-6
• 发表日期: 2026-03-09
• 关键词: integer programming; Sparse integral solutions; semigroups; Approximate caratheodory; RECOVERY; bounds

摘要

This paper deals with the following question: Suppose that there exist an integer or a non-negative integer solution x to a system Ax = b, where the number of non-zero components of x is n. The target is, for a given natural number k < n, to approximate b with Ay where y is an integer or non-negative integer solution with at most k nonzero components. We establish upper bounds for this question in general. In specific cases, these bounds are tight. If we view the approximation quality as a function of the parameter k, then the paper explains why the quality of the approximation increases exponentially as k goes to n. This paper is a complete version of an extended abstract that appeared at the 26th International Conference on Integer Programming and Combinatorial Optimization (IPCO) [28].