Article (Scientific journals)
Approximation algorithms for integer covering problems via greedy column generation
Crama, Yves; Van de Klundert, Joris
1994In RAIRO: Recherche Opérationnelle, 28, p. 283-302
Peer Reviewed verified by ORBi
 

Files


Full Text
Approximation set covering RAIRO_1994__28_3_283_0.pdf
Publisher postprint (1.9 MB)
Download

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
integer programming; covering problem; greedy heuristic; approximation algorithms; column generation
Abstract :
[en] Many combinatorial optimization problems can be formulated as covering problems. In some cases, this covering 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. We propose a modification of the greedy algorithm in which the column generation subproblem is solved approximately, within a factor α. We derive upper bounds for the worst case ratio of this algorithm and related polynomial approximation algorithms.
Disciplines :
Quantitative methods in economics & management
Author, co-author :
Crama, Yves  ;  Université de Liège > HEC-Ecole de gestion : UER > Recherche opérationnelle et gestion de la production
Van de Klundert, Joris
Language :
English
Title :
Approximation algorithms for integer covering problems via greedy column generation
Publication date :
1994
Journal title :
RAIRO: Recherche Opérationnelle
ISSN :
0399-0559
eISSN :
1290-3868
Publisher :
EDP Sciences, Paris, France
Volume :
28
Pages :
283-302
Peer reviewed :
Peer Reviewed verified by ORBi
Available on ORBi :
since 14 November 2016

Statistics


Number of views
51 (2 by ULiège)
Number of downloads
103 (1 by ULiège)

Bibliography


Similar publications



Contact ORBi