TUBITAK Destekli Projelerden Çıkan Yayınlar Topluluğu
Yayınlanmış 1 Ocak 2009 | Sürüm v1
Dergi makalesi Açık

GENERATING FACETS FOR THE INDEPENDENCE SYSTEM POLYTOPE

Oluşturanlar

  • 1. Univ Paris 06, Lab LIP6, F-75005 Paris, France
  • 2. Univ Libre Bruxelles, Dept Informat, B-1050 Brussels, Belgium
  • 3. Univ Paris 09, Lab LAMSADE, CNRS, UMR 7024, F-75775 Paris, France
  • 4. Bilkent Univ, Dept Ind Engn, TR-06800 Ankara, Turkey

Açıklama

In this paper, we present procedures to obtain facet-defining inequalities for the independence system polytope. These procedures are defined for inequalities which are not necessarily rank inequalities. We illustrate the use of these procedures by deriving strong valid inequalities for the acyclic induced subgraph, triangle free induced subgraph, bipartite induced subgraph, and knapsack polytopes. Finally, we derive a new family of facet-defining inequalities for the independence system polytope by adding a set of edges to antiwebs.

Dosyalar

bib-a76d4d58-78ca-40e7-aa02-bb9ecf13e8d8.txt

Dosyalar (169 Bytes)

Ad Boyut Hepisini indir
md5:4c5d567e49a5f174a89770dcd21b3656
169 Bytes Ön İzleme İndir