caa a22 4500 445804777 CHVBK 20180317145153.0 cr unu---uuuuu 170323e20110101xx s 000 0 eng 10.1007/s00453-010-9408-y doi (NATIONALLICENCE)springer-10.1007/s00453-010-9408-y Approximation Algorithms for k -hurdle Problems [Elektronische Daten] [Brian Dean, Adam Griffis, Ojas Parekh, Adam Whitley] The polynomial-time solvable k-hurdle problem is a natural generalization of the classical s-t minimum cut problem where we must select a minimum-cost subset S of the edges of a graph such that |p∩S|≥k for every s-t path p. In this paper, we describe a set of approximation algorithms for "k-hurdle” variants of the NP-hard multiway cut and multicut problems. For the k-hurdle multiway cut problem with r terminals, we give two results, the first being a pseudo-approximation algorithm that outputs a (k−1)-hurdle solution whose cost is at most that of an optimal solution for k hurdles. Secondly, we provide a $2(1-\frac{1}{r})$-approximation algorithm based on rounding the solution of a linear program, for which we give a simple randomized half-integrality proof that works for both edge and vertex k-hurdle multiway cuts that generalizes the half-integrality results of Garg et al.for the vertex multiway cut problem. We also describe an approximation-preserving reduction from vertex cover as evidence that it may be difficult to achieve a better approximation ratio than $2(1-\frac{1}{r})$. For the k-hurdle multicut problem in an n-vertex graph, we provide an algorithm that, for any constant ε>0, outputs a ⌈(1−ε)k⌉-hurdle solution of cost at most O(log n) times that of an optimal k-hurdle solution, and we obtain a 2-approximation algorithm for trees. Springer Science+Business Media, LLC, 2010 Multiway cut nationallicence Multicut nationallicence Approximation algorithm nationallicence Randomized rounding nationallicence Dean Brian School of Computing, Clemson University, Clemson, SC, USA aut Griffis Adam School of Computing, Clemson University, Clemson, SC, USA aut Parekh Ojas Mathematics and Computer Science Department, Emory University, Atlanta, GA, USA aut Whitley Adam School of Computing, Clemson University, Clemson, SC, USA aut Algorithmica Springer-Verlag 59/1(2011-01-01), 81-93 0178-4617 59:1<81 2011 59 453 https://doi.org/10.1007/s00453-010-9408-y text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-010-9408-y text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Dean Brian School of Computing, Clemson University, Clemson, SC, USA aut NATIONALLICENCE 700 1- Griffis Adam School of Computing, Clemson University, Clemson, SC, USA aut NATIONALLICENCE 700 1- Parekh Ojas Mathematics and Computer Science Department, Emory University, Atlanta, GA, USA aut NATIONALLICENCE 700 1- Whitley Adam School of Computing, Clemson University, Clemson, SC, USA aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 59/1(2011-01-01), 81-93 0178-4617 59:1<81 2011 59 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer