TUBITAK Destekli Projelerden Çıkan Yayınlar Topluluğu
Published January 1, 2009 | Version v1
Journal article Open

GENERATING FACETS FOR THE INDEPENDENCE SYSTEM POLYTOPE

Creators

  • 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

Description

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.

Files

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

Files (169 Bytes)

Name Size Download all
md5:4c5d567e49a5f174a89770dcd21b3656
169 Bytes Preview Download