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 (m) and the largest absolute value of the entries of the constraint matrix (∆). The running time is exponential in m, and becomes pseu... View More