New Networks Special Issue on Network Analytics and Optimization

The journal Networks recently published a Special Issue on Network Analytics and Optimization devoted to recent research in the areas of network analysis and optimization. The special issue contains a selection of high-quality papers presented at two conferences: International Network Optimization Conference 2019 and the 30th European Conference on Operational Research. 

Bernard Fortz and Luis Gouveia served as Guest Editors for the papers presented at International Network Optimization Conference held on June 12–14, 2019, in Avignon, France. The papers from this conference published in the journal are as follows: 

Anapolska et al. study the minimum color-degree perfect b-matching problem. They show the problem is NP-hard on bipartite graphs and also provide some inapproximability results. Then they propose several polynomial-time dynamic programming algorithms for special cases. Published Open Access.

Cambier et al. consider optimization of the network expansion plan of a mobile telecommunication company, including the deployment and/or reinforcement of several technologies. The dynamics of subscribers’ adoption of a technology are included in the model and can be influenced by subsidies from the operator. The authors propose a mathematical model and a heuristic strategy to solve it, and they then present a case study for 3G and 4G technologies.

Marciano et al. study the edge reversal strategy for scheduling, in which the objective is to minimize or maximize the concurrency of a distributed system. The complexity of the problem is studied as well as several approximation algorithms. A case study on assembling musical phrases is also presented. The conference version of this paper was awarded the Best Student Paper Award at INOC 2019.

Tomaszewski et al. propose a solution approach for semi-stable routing in Software-Defined Networks, where reconfigurations cannot be too frequent. The paper focuses on the issue of deciding when and how to reconfigure the network as traffic evolves.

Christina Büsing and Markus Leitner served as Guest Editors for the papers presented at the 30th European Conference on Operational Research, held on June 23–26, 2019, in Dublin, Ireland. These papers present theoretical results concerning the structure and complexity of network problems as well as timely and relevant applications in the area of social networks. The following papers come from the conference. 

De Melo et al. study the complexity of a simple two-commodity integral flow problem. They prove that the problem is NP-hard on undirected graphs even if one of the demands is unitary. This closes the gap between the polynomially-solvable case when both demands are unitary and the NP-hard case when both demands are not unitary. Furthermore, they investigate the complexity of the strict terminal connection problem, combining the full Steiner tree problem with a restriction on the branching nodes.

Gudapati et al. investigate the densest subgraph problem. In a first step, they present an efficient implementation of a greedy algorithm, which is able to cope with large-scale instances that cannot be solved in reasonable time by an exact method. In a second step, they combine the greedy algorithm with ideas of an exact solution approach. In a computational study, they show that the new algorithm is able to rapidly compute optimal or near-optimal solutions for most of the considered test instances. Published Open Access.

Raghavan and Zhang study the weighted target set selection (WTSS) problem on cycles and trees. For trees, they provide a linear-time dynamic programming algorithm and a tight and compact extended formulation. This formulation is then projected onto the space of node variables to derive a new formulation, describing the polytope of the WTSS in its natural variable space. Similar techniques are used to obtain a complete description of the polytope for the WTSS problem on cycles. These insights are used to obtain new strong formulations for the WTSS problem on arbitrary graphs.

More Details