2026-07-23T12:54:51Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18131 2024-03-06T11:01:06Z ddc:004 open_access

Finding Almost Tight Witness Trees Hyatt-Denesik, Dylan Jabal Ameli, Afrouz Sanità, Laura Algorithms Network Design Approximation This paper addresses a graph optimization problem, called the Witness Tree problem, which seeks a spanning tree of a graph minimizing a certain non-linear objective function. This problem is of interest because it plays a crucial role in the analysis of the best approximation algorithms for two fundamental network design problems: Steiner Tree and Node-Tree Augmentation. We will show how a wiser choice of witness trees leads to an improved approximation for Node-Tree Augmentation, and for Steiner Tree in special classes of graphs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dylan Hyatt-Denesik and Afrouz Jabal Ameli and Laura Sanità 2023 Is Part Of LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2023.79 urn:nbn:de:0030-drops-181314 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.79 eng https://creativecommons.org/licenses/by/4.0/legalcode