Approximation algorithms for integer covering problems via greedy column generation

Approximation algorithms for integer covering problems via greedy column generation

0.00 Avg rating0 Votes
Article ID: iaor19971073
Country: France
Volume: 28
Issue: 3
Start Page Number: 283
End Page Number: 302
Publication Date: Jul 1994
Journal: RAIRO Operations Research
Authors: ,
Keywords: heuristics
Abstract:

Many combinatorial problems can be formulated as covering problems. In some cases, e.g. the cutting stock problem, this formulation is not polynomial in the input size of the original problem. In order to solve the problem approximately one can apply the Greedy algorithm to the covering 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. The authors propose a modification of the Greedy algorithm in which the column generation subproblem is solved approximately, within a factor α. They derive upper bounds for the worst case ratio of this algorithm and related polynomial approximation algorithms.

Reviews

Required fields are marked *. Your email address will not be published.