2024/10/31 by Stefan Kuhlmann, Kuhlmann, Stefan, Timm Oertel +3
Computer Science · Decision Sciences · #Rough Sets and Fuzzy Logic #Advanced Algebra and Logic #Fuzzy and Soft Set Theory
paper · pdf · doi:10.48550/arxiv.2410.23990
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 non-zero 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).