Approximation algorithms for integer programming with resource augmentation
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912797213851648 |
|---|---|
| author | Brinkop, Hauke Chen, Hua Chen, Lin Jansen, Klaus Zhang, Guochuan |
| author_facet | Brinkop, Hauke Chen, Hua Chen, Lin Jansen, Klaus Zhang, Guochuan |
| contents | The classic algorithm [Papadimitriou, J.ACM '81] for IPs has a running time $n^{O(m)}(m\cdot\max\{Δ,\|\textbf{b}\|_{\infty}\})^{O(m^2)}$, where $m$ is the number of constraints, $n$ is the number of variables, and $Δ$ and $\|\textbf{b}\|_{\infty}$ are, respectively, the largest absolute values among the entries in the constraint matrix and the right-hand side vector of the constraint. The running time is exponential in $m$, and becomes pseudo-polynomial if $m$ is a constant. In recent years, there has been extensive research on FPT (fixed parameter tractable) algorithms for the so-called $n$-fold IPs, which may possess a large number of constraints, but the constraint matrix satisfies a specific block structure. It is remarkable that these FPT algorithms take as parameters $Δ$ and the number of rows and columns of some small submatrices. If $Δ$ is not treated as a parameter, then the running time becomes pseudo-polynomial even if all the other parameters are taken as constants.
This paper explores the trade-off between time and accuracy in solving an IP. We show that, for arbitrary small $\varepsilon>0$, there exists an algorithm for IPs with $m$ constraints that runs in ${f(m,\varepsilon)}\cdot\textnormal{poly}(|I|)$ time, and returns a near-feasible solution that violates the constraints by at most $\varepsilonΔ$. Furthermore, for $n$-fold IPs, we establish a similar result -- our algorithm runs in time that depends on the number of rows and columns of small submatrices together with $1/\varepsilon$, and returns a solution that slightly violates the constraints. Meanwhile, both solutions guarantee that their objective values are no worse than the corresponding optimal objective values satisfying the constraints. As applications, our results can be used to obtain additive approximation schemes for multidimensional knapsack as well as scheduling. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_24302 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Approximation algorithms for integer programming with resource augmentation Brinkop, Hauke Chen, Hua Chen, Lin Jansen, Klaus Zhang, Guochuan Optimization and Control The classic algorithm [Papadimitriou, J.ACM '81] for IPs has a running time $n^{O(m)}(m\cdot\max\{Δ,\|\textbf{b}\|_{\infty}\})^{O(m^2)}$, where $m$ is the number of constraints, $n$ is the number of variables, and $Δ$ and $\|\textbf{b}\|_{\infty}$ are, respectively, the largest absolute values among the entries in the constraint matrix and the right-hand side vector of the constraint. The running time is exponential in $m$, and becomes pseudo-polynomial if $m$ is a constant. In recent years, there has been extensive research on FPT (fixed parameter tractable) algorithms for the so-called $n$-fold IPs, which may possess a large number of constraints, but the constraint matrix satisfies a specific block structure. It is remarkable that these FPT algorithms take as parameters $Δ$ and the number of rows and columns of some small submatrices. If $Δ$ is not treated as a parameter, then the running time becomes pseudo-polynomial even if all the other parameters are taken as constants. This paper explores the trade-off between time and accuracy in solving an IP. We show that, for arbitrary small $\varepsilon>0$, there exists an algorithm for IPs with $m$ constraints that runs in ${f(m,\varepsilon)}\cdot\textnormal{poly}(|I|)$ time, and returns a near-feasible solution that violates the constraints by at most $\varepsilonΔ$. Furthermore, for $n$-fold IPs, we establish a similar result -- our algorithm runs in time that depends on the number of rows and columns of small submatrices together with $1/\varepsilon$, and returns a solution that slightly violates the constraints. Meanwhile, both solutions guarantee that their objective values are no worse than the corresponding optimal objective values satisfying the constraints. As applications, our results can be used to obtain additive approximation schemes for multidimensional knapsack as well as scheduling. |
| title | Approximation algorithms for integer programming with resource augmentation |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2512.24302 |