## Steiner tree 1.39-approximation in practice

Autor(en): | Beyer, S. Chimani, M. |

Herausgeber: | Dvorak, Z. Kofron, J. Hlineny, P. Matula, P. Pala, K. Jaros, J. Korenek, J. |

Stichwörter: | Algorithms; Approximation algorithms; Matrix algebra, Implementation aspects; Integral solutions; LP relaxation; Matroid theory; Parameter choice; Running time; Steiner trees, Trees (mathematics) |

Erscheinungsdatum: | 2014 |

Herausgeber: | Springer Verlag |

Journal: | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |

Volumen: | 8934 |

Startseite: | 60 |

Seitenende: | 72 |

Zusammenfassung: | We consider the currently strongest Steiner tree approximation algorithm that has recently been published by Goemans, Olver, Rothvoβ and Zenklusen (2012). It first solves a hypergraphic LP relaxation and then applies matroid theory to obtain an integral solution. The cost of the resulting Steiner tree is at most (1.39 ε)-times the cost of an optimal Steiner tree where ε tends to zero as some parameter k tends to infinity. However, the degree of the polynomial running time depends on this constant k, so only small k are tractable in practice. The algorithm has, to our knowledge, not been implemented and evaluated in practice before. We investigate different implementation aspects and parameter choices of the algorithm and compare tuned variants to an exact LP-based algorithm as well as to fast and simple 2-approximations. © Springer International Publishing Switzerland 2014. |

Beschreibung: | Conference of 9th International Doctoral Workshop on Mathematical and Engineering Methods in Computer Science, MEMICS 2014 ; Conference Date: 17 October 2014 Through 19 October 2014; Conference Code:112649 |

ISBN: | 9783319148953 |

ISSN: | 03029743 |

DOI: | 10.1007/978-3-319-14896-0_6 |

Externe URL: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-84927918115&doi=10.1007%2f978-3-319-14896-0_6&partnerID=40&md5=681026cd04e519eb9c6db817d3a9f926 |

Show full item record