Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2512.02571 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910019218309120 |
|---|---|
| author | Grobben, Kobe Moura, Phablo F. S. Yaman, Hande |
| author_facet | Grobben, Kobe Moura, Phablo F. S. Yaman, Hande |
| contents | This paper presents an algorithmic study of a class of covering mixed-integer linear programming problems which encompasses classic cover problems, including multidimensional knapsack, facility location and supplier selection problems. We first show some properties of optimal solutions, which are then used to decompose the problem into instances of the multidimensional knapsack cover problem with a single continuous variable per dimension. The proposed decomposition is used to design a polynomial-time approximation scheme for the problem with a fixed number of constraints. To the best of our knowledge, this is the first approximation scheme for such a general class of covering mixed-integer linear programs. Moreover, we design a fully polynomial-time approximation scheme and an approximate linear programming formulation for the case with a single constraint. These results improve upon the previously best-known 2-approximation algorithm for the knapsack cover problem with a single continuous variable. Finally, we show a perfect compact formulation for the case where all variables have the same lower and upper bounds. Analogous results are derived for the packing and more general variants of the problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_02571 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Covering and packing mixed-integer linear programs with a fixed number of constraints: Approximation and convex hull Grobben, Kobe Moura, Phablo F. S. Yaman, Hande Data Structures and Algorithms 68W25, 68W40, 90Cxx This paper presents an algorithmic study of a class of covering mixed-integer linear programming problems which encompasses classic cover problems, including multidimensional knapsack, facility location and supplier selection problems. We first show some properties of optimal solutions, which are then used to decompose the problem into instances of the multidimensional knapsack cover problem with a single continuous variable per dimension. The proposed decomposition is used to design a polynomial-time approximation scheme for the problem with a fixed number of constraints. To the best of our knowledge, this is the first approximation scheme for such a general class of covering mixed-integer linear programs. Moreover, we design a fully polynomial-time approximation scheme and an approximate linear programming formulation for the case with a single constraint. These results improve upon the previously best-known 2-approximation algorithm for the knapsack cover problem with a single continuous variable. Finally, we show a perfect compact formulation for the case where all variables have the same lower and upper bounds. Analogous results are derived for the packing and more general variants of the problem. |
| title | Covering and packing mixed-integer linear programs with a fixed number of constraints: Approximation and convex hull |
| topic | Data Structures and Algorithms 68W25, 68W40, 90Cxx |
| url | https://arxiv.org/abs/2512.02571 |