论文标题
网络设计的光谱方法
A Spectral Approach to Network Design
论文作者
论文摘要
我们提出了一种设计网络设计问题的近似算法的光谱方法。我们观察到，基本的数学问题是光谱舍入问题，这些问题是在光谱稀疏和差异理论中研究的。我们扩展了这些结果以纳入其他非负线性约束，并表明它们可用于显着扩展可以解决的网络设计问题的范围。我们用于光谱舍入的算法是基于遗憾最小化框架的迭代随机舍入算法。在某些情况下，这提供了一种替代的光谱算法，以实现经典可生存的网络设计问题的恒定因子近似，并部分回答了班萨尔关于具有浓度属性的生存网络设计的问题。我们还显示了光谱舍入结果的许多其他应用，包括加权实验设计和添加光谱稀疏。
We present a spectral approach to design approximation algorithms for network design problems. We observe that the underlying mathematical questions are the spectral rounding problems, which were studied in spectral sparsification and in discrepancy theory. We extend these results to incorporate additional non-negative linear constraints, and show that they can be used to significantly extend the scope of network design problems that can be solved. Our algorithm for spectral rounding is an iterative randomized rounding algorithm based on the regret minimization framework. In some settings, this provides an alternative spectral algorithm to achieve constant factor approximation for the classical survivable network design problem, and partially answers a question of Bansal about survivable network design with concentration property. We also show many other applications of the spectral rounding results, including weighted experimental design and additive spectral sparsification.
