APPROXIMATION ALGORITHMS FOR INTEGER COVERING PROBLEMS VIA GREEDY COLUMN GENERATION

Many combinatorial problems can be formulated as covering problems. In some cases, e.g. the cutting stock problem, this formulation is not p olynomial in the input size of the original problem. In order to solve the problem approximately one can apply the Greedy algorithm to the c overing formulation. In this case, the column generation subproblem is to determine which column the Greedy algorithm chooses. This problem might be NP-hard in itself. We propose a modification of the Greedy al gorithm in which the column generation subproblem is solved approximat ely, within a factor alpha. We derive upper bounds for the worst case ratio of this algorithm and related polynomial approximation algorithm s.