Packing and covering with linear programming: A survey.
Ries, Bernard; Cornaz, Denis; Bentz, Cédric (2013), Packing and covering with linear programming: A survey., European Journal of Operational Research, 227, 3, p. 409-422. http://dx.doi.org/10.1016/j.ejor.2012.11.045
Type
Article accepté pour publication ou publiéDate
2013Journal name
European Journal of Operational ResearchVolume
227Number
3Publisher
Elsevier
Pages
409-422
Publication identifier
Metadata
Show full item recordAbstract (EN)
This paper considers the polyhedral results and the min–max results on packing and covering problems of the decade. Since the strong perfect graph theorem (published in 2006), the main such results are available for the packing problem, however there are still important polyhedral questions that remain open. For the covering problem, the main questions are still open, although there has been important progress. We survey some of the main results with emphasis on those where linear programming and graph theory come together. They mainly concern the covering of cycles or dicycles in graphs or signed graphs, either with vertices or edges; this includes the multicut and integral multiflow problems. [Copyright &y& Elsevier]Subjects / Keywords
Hypergraph; Min–max relation; Polyhedra; Packing; Covering; Linear programmingRelated items
Showing items related by title and author.
-
Bazgan, Cristina; Bentz, Cédric; Picouleau, Christophe; Ries, Bernard (2015) Article accepté pour publication ou publié
-
Bentz, Cédric; Costa, Marie-Christine; Ries, Bernard; de Werra, Dominique; Picouleau, Christophe; Zenklusen, Rico (2010) Article accepté pour publication ou publié
-
Bentz, Cédric; Costa, Marie-Christine; Picouleau, Christophe; Ries, Bernard; de Werra, Dominique (2012) Article accepté pour publication ou publié
-
Ries, Bernard; Picouleau, Christophe; de Werra, Dominique; Costa, Marie-Christine; Bentz, Cédric (2011) Chapitre d'ouvrage
-
Bentz, Cédric; Costa, Marie-Christine; de Werra, Dominique; Picouleau, Christophe; Ries, Bernard; Zenklusen, R. (2009) Communication / Conférence