Print Email Facebook Twitter Optimization problems in correlated networks Title Optimization problems in correlated networks Author Yang, S. Trajanovski, S. Kuipers, F.A. Faculty Electrical Engineering, Mathematics and Computer Science Department Intelligent Systems Date 2016-01-22 Abstract Background 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. Methods 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. Results and Conclusions 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. Subject shortest pathmin-cutcorrelated networksstochastic link weightsOA-Fund TU Delft To reference this document use: http://resolver.tudelft.nl/uuid:5da08269-1324-4fb6-9b1b-c13d044e362f Publisher SpringerOpen ISSN 2197-4314 Source https://doi.org/10.1186/s40649-016-0026-y Source Computational Social Networks, 3 (1), 2016 Part of collection Institutional Repository Document type journal article Rights © 2016 The Author(s)This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/) Files PDF Kuipers_2016.pdf 1.61 MB Close viewer /islandora/object/uuid:5da08269-1324-4fb6-9b1b-c13d044e362f/datastream/OBJ/view