Optimization problems in correlated networks
Optimization problems in correlated networks
复制标题
相关网络中的优化问题
DOI：
--
复制
发表时间：
2015
影响因子：
--
通讯作者：
F. Kuipers
中科院分区：
文献类型：
--
作者：
Song Yang;S. Trajanovski;F. Kuipers
解决最短路径和最小割问题是实现高性能和稳健通信网络的关键。这些问题在确定性和无关联网络中经常在其原始形式以及若干受限变体中被研究。然而，在现实世界的网络中，由于空间或时间原因，链路权重（例如，延迟、带宽、故障概率）往往是相关的，并且这些相关的链路权重一起表现出不同的行为方式，并且并不总是像通常假设的那样具有可加性。在本文中，我们首先提出两个相关链路权重模型，即（1）确定性相关模型和（2）（对数凹）随机相关模型。随后，我们研究在这两个相关模型下的最短路径问题和最小割问题。我们证明在确定性相关模型下这两个问题是NP难的，甚至在多项式时间内不能被任意近似。然而，在（受限的）节点确定性相关模型下这两个问题可在多项式时间内求解，并且在（对数凹）随机相关模型下可通过凸优化求解。
Solving the shortest path and min-cut problems are key in achieving high-performance and robust communication networks. Those problems have often been studied in deterministic and uncorrelated networks both in their original formulations as well as in several constrained variants. However, in real-world networks, link weights (e.g., delay, bandwidth, failure probability) are often correlated due to spatial or temporal reasons, and these correlated link weights together behave in a different manner and are not always additive, as commonly assumed. In this paper, we first propose two correlated link weight models, namely (1) the deterministic correlated model and (2) the (log-concave) stochastic correlated model. Subsequently, we study the shortest path problem and the min-cut problem under these two correlated models. We prove that these two problems are NP-hard under the deterministic correlated model, and even cannot be approximated to arbitrary degree in polynomial time. However, these two problems are solvable in polynomial time under the (constrained) nodal deterministic correlated model, and can be solved by convex optimization under the (log-concave) stochastic correlated model.