Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Hypergraphic LP Relaxations for Steiner Trees
 
conference paper

Hypergraphic LP Relaxations for Steiner Trees

Chakrabarty, Deeparnab
•
Könemann, Jochen
•
Pritchard, David  
Eisenbrand, F.  
•
Shepherd, F. B.
2010
Proc. 14th Conference on Integer Programming and Combinatorial Optimization (IPCO)
14th Conference on Integer Programming and Combinatorial Optimization (IPCO)

We investigate hypergraphic LP relaxations for the Steiner tree problem, primarily the partition LP relaxation introduced by Koenemann et al. [Math. Programming, 2009]. Specifically, we are interested in proving upper bounds on the integrality gap of this LP, and studying its relation to other linear relaxations. Our results are the following. Structural results: We extend the technique of uncrossing, usually applied to families of sets, to families of partitions. As a consequence we show that any basic feasible solution to the partition LP formulation has sparse support. Although the number of variables could be exponential, the number of positive variables is at most the number of terminals. Relations with other relaxations: We show the equivalence of the partition LP relaxation with other known hypergraphic relaxations. We also show that these hypergraphic relaxations are equivalent to the well studied bidirected cut relaxation, if the instance is quasibipartite. Integrality gap upper bounds: We show an upper bound of sqrt(3) ~ 1.729 on the integrality gap of these hypergraph relaxations in general graphs. In the special case of uniformly quasibipartite instances, we show an improved upper bound of 73/60 ~ 1.216. By our equivalence theorem, the latter result implies an improved upper bound for the bidirected cut relaxation as well.

  • Details
  • Metrics
Type
conference paper
DOI
10.1007/978-3-642-13036-6_29
ArXiv ID

0910.0281

Author(s)
Chakrabarty, Deeparnab
Könemann, Jochen
Pritchard, David  
Editors
Eisenbrand, F.  
•
Shepherd, F. B.
Date Issued

2010

Publisher

Springer

Published in
Proc. 14th Conference on Integer Programming and Combinatorial Optimization (IPCO)
Series title/Series vol.

Lecture Notes in Computer Science; 6080

Start page

383

End page

396

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DISOPT  
Event nameEvent placeEvent date
14th Conference on Integer Programming and Combinatorial Optimization (IPCO)

Lausanne, Switzerland

June 9-11, 2010

Available on Infoscience
August 21, 2010
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/52337
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés