.png){kind=icon}
.png){kind=icon}
Return
Approximation Algorithms for Integer Programming with Resource Augmentation
.png){kind=icon}
PRE
AI
DOI：10.4230/LIPIcs.STACS.2026.20.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Solving a general integer program (IP) is NP-hard. The classic algorithm [Papadimitriou, J.ACM '81] for IPs has a running time n(O(m))( m center dot max{Delta, parallel to b parallel to(infinity)})(O(m2)), where m is the number of constraints, n is the number of variables, and Delta and parallel to b parallel to(infinity) 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 Delta 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 epsilon > 0, there exists an algorithm for IPs with m constraints that runs in f( m, epsilon) center dot poly(|I|) time, and returns a near-feasible solution that violates the constraints by at most epsilon Delta. 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/epsilon, 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.
Keywords:
Approximation algorithms
Resource augmentation
Integer programs
n-fold IPs
Journal
4
IF:
0
Papers:
81
Citations:
0
View more organizations