000150508 001__ 150508
000150508 005__ 20190812205422.0
000150508 0247_ $$2doi$$a10.1007/978-3-642-13036-6_29
000150508 02470 $$a0910.0281$$2ArXiv
000150508 037__ $$aCONF
000150508 245__ $$aHypergraphic LP Relaxations for Steiner Trees
000150508 269__ $$a2010
000150508 260__ $$bSpringer$$c2010
000150508 336__ $$aConference Papers
000150508 490__ $$aLecture Notes in Computer Science$$v6080
000150508 520__ $$aWe 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.
000150508 700__ $$aChakrabarty, Deeparnab
000150508 700__ $$aKönemann, Jochen
000150508 700__ $$0243822$$g198587$$aPritchard, David
000150508 7112_ $$dJune 9-11, 2010$$cLausanne, Switzerland$$a14th Conference on Integer Programming and Combinatorial Optimization (IPCO)
000150508 720_1 $$aEisenbrand, F.$$eed.$$g183121$$0240331
000150508 720_1 $$aShepherd, F. B.$$eed.
000150508 773__ $$tProc. 14th Conference on Integer Programming and Combinatorial Optimization (IPCO)$$q383-396
000150508 909C0 $$xU11879$$pDISOPT$$0252111
000150508 909CO $$ooai:infoscience.tind.io:150508$$qGLOBAL_SET$$pconf$$pSB
000150508 917Z8 $$x198587
000150508 937__ $$aEPFL-CONF-150508
000150508 973__ $$rREVIEWED$$sPUBLISHED$$aEPFL
000150508 980__ $$aCONF