Finding almost tight witness trees

• 成果类型: Article; Early Access
• 署名作者: Hyatt-Denesik, Dylan; Ameli, Afrouz Jabal; Sanita, Laura
• 署名单位: Eindhoven University of Technology; Bocconi University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610; 1436-4646
• DOI: 10.1007/s10107-026-02328-2
• 发表日期: 2026-02-05
• 关键词: approximation algorithms; Connectivity augmentation; Steiner tree; Witness trees; augmentation

摘要

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.