.png){kind=icon}
.png){kind=icon}
Return
Sparse approximation in lattices and semigroups
.png){kind=icon}
PRE
AI
DOI：10.1007/s10107-026-02340-6.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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].
Keywords:
Integer programming
Sparse integral solutions
Semigroups
Approximate caratheodory
Journal
M
IF:
2.5
Papers:
85
Citations:
0