Approximation Algorithms for Integer Programming with Resource Augmentation

Solving a general integer program (IP) is NP-hard.
The classic algorithm [Papadimitriou, J.ACM '81] for IPs has a running time depending on the number of constraints and the largest absolute value of the entries of the constraint matrix.
The running time is exponential in the number of constraints and becomes pseudo-polynomial if the number is constraints is 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 an arbitrary number of constraints, but the constraint matrix satisfies a specific block structure.
It is remarkable that these FPT algorithms take the largest absolute value value of the constraint matrix as a parameter, together with other parameters including the number of rows/columns of some small submatrices.
If largest absolute value value of the constraint matrix 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 epsilon greater 0, there exists an algorithm that returns a near-feasible solution, that is, a solution that violates the constraints by at most epsilon times the largest absolute value of the constraint matrix; and whose running time is bounded by a computable function in the number of constraints and the inverse of epsilon times a polynomial in the input encoding.
Furthermore, for n-fold IPs, we establish a similar result -- our algorithm's running time is bounded by a computable function in the number of rows and columns of the small submatrices and the inverse of epsilon; and returns a solution that slightly violates the constraints.
We show that our results can be used to obtain additive approximation schemes for multidimensional knapsack as well as scheduling.

Preview

Logo BII

Rights

Use and reproduction:

No license. The provisions of the German Copyright Act (UrhG) apply.

Please note that individual components of the publication may be subject to other licensing or copyright conditions.

Cite

Citation style:
Could not load citation form.