Home > Hypergraphic LP Relaxations for Steiner Trees > HTML MARC |

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