Approximation algorithms for integer programming with resource augmentation

Hauke Brinkop, Hua Chen, Lin Chen +2

The classic algorithm [Papadimitriou, J.ACM '81] for IPs has a running time $n^{O(m)}(m\cdot \max \{\Delta ,\Vert \text{b}{\Vert }_{\infty }\}{)}^{O(m^2)}$, where $m$ is the number of constraints, $n…