Open Access
Issue
Published:
*04 December 2023*

Keywords:

Maximum Capacity Path (MCP), network expansion, Internet routing, polynomial-time algorithms
Cite this article:

Deaconu AM, Tayyebi J.
Increasing the Maximum Capacity Path in a Network and Its Application for Improving the Connection Between Two Routers.
Tsinghua Science and Technology,
2024, 29(3): 753-765.
https://doi.org/10.26599/TST.2023.9010055
Download citation

135

Views

12

Downloads

Citations

0

Crossref

0

WoS

0

Scopus

0

CSCD

This paper addresses the problem of improving the optimal value of the Maximum Capacity Path (MCP) through expansion in a flexible network, and minimizing the involved costs. The only condition applied to the cost functions is to be non-decreasing monotone. This is a non-restrictive condition, reflecting the reality in practice, and is considered for the first time in the literature. Moreover, the total cost of expansion is a combination of max-type cost (e.g., for supervision) and sum-type cost (e.g. for building infrastructures, price of materials, price of labor, etc.). For this purpose, two types of strategies are combined: (I) increasing the capacity of the existing arcs, and (II) adding potential new arcs. Two different problems are introduced and solved. Both the problems have immediate applications in Internet routing infrastructure. The first one is to extend the network, so that the capacity of an MCP in the modified network becomes equal to a prescribed value, therefore the cost of modifications is minimized. A strongly polynomial-time algorithm is deduced to solve this problem. The second problem is a network expansion under a budget constraint, so that the capacity of an MCP is maximized. A weakly polynomial-time algorithm is presented to deal with it. In the special case when all the costs are linear, a Meggido’s parametric search technique is used to develop an algorithm for solving the problem in strongly polynomial time. This new approach has a time complexity of

menu

Abstract

Full text

Outline

About this article

This paper addresses the problem of improving the optimal value of the Maximum Capacity Path (MCP) through expansion in a flexible network, and minimizing the involved costs. The only condition applied to the cost functions is to be non-decreasing monotone. This is a non-restrictive condition, reflecting the reality in practice, and is considered for the first time in the literature. Moreover, the total cost of expansion is a combination of max-type cost (e.g., for supervision) and sum-type cost (e.g. for building infrastructures, price of materials, price of labor, etc.). For this purpose, two types of strategies are combined: (I) increasing the capacity of the existing arcs, and (II) adding potential new arcs. Two different problems are introduced and solved. Both the problems have immediate applications in Internet routing infrastructure. The first one is to extend the network, so that the capacity of an MCP in the modified network becomes equal to a prescribed value, therefore the cost of modifications is minimized. A strongly polynomial-time algorithm is deduced to solve this problem. The second problem is a network expansion under a budget constraint, so that the capacity of an MCP is maximized. A weakly polynomial-time algorithm is presented to deal with it. In the special case when all the costs are linear, a Meggido’s parametric search technique is used to develop an algorithm for solving the problem in strongly polynomial time. This new approach has a time complexity of

[1]

H. N. Gabow and R. E. Tarjan, Algorithms for two bottleneck optimization problems, *J. Algorithm.*, vol. 9, no. 3, pp. 411–417, 1988.

[2]

N. Shacham, Multicast routing of hierarchical data, in *Proc. Discovering a New World of Communications*, Chicago, IL, USA, 1992, pp. 1217–1221.

[3]

M. Schulze, A new monotonic, clone-independent, reversal symmetric, and condorcet-consistent single-winner election method, *Soc. Choice Welfare*, vol. 36, no. 2, pp. 267–303, 2011.

[4]

E. Fernandez, R. Garfinkel, and R. Arbiol, Mosaicking of aerial photographic maps via seams defined by bottleneck shortest paths, *Oper. Res*., vol. 46, no. 3, pp. 293–304, 1998.

[5]

E. Ullah, K. Lee, and S. Hassoun, An algorithm for identifying dominant-edge metabolic pathways, in *Proc. IEEE/ACM Int. Conf. Computer-Aided Design-Digest of Technical Papers*, San Jose, CA, USA, 2009, pp. 144–150.

[6]

R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, *Network Flows : Theory*, *Algorithms and Applications*. Englewood Cliffss, NJ, USA: Prentice Hall, 1993.

[7]

J. Tayyebi and A. Deaconu, Expanding maximum capacity path under weighted sum-type distances, *AIMS Math.*, vol. 6, no. 4, pp. 3996–4010, 2021.

[8]

A. M. Deaconu and J. Tayyebi, Inverse maximum capacity path problems under sum-type and max- type distances and their practical application to transportation networks, *IEEE Access*, vol. 8, pp. 225957–225966, 2020.

[9]

A. M. Deaconu and L. Majercsik, Flow increment through network expansion, *Mathematics*, vol. 9, no. 18, p. 2308, 2021.

[10]

Y. Hu, X. Zhao, J. Liu, B. Liang, and C. Ma, An efficient algorithm for solving minimum cost flow problem with complementarity slack conditions, *Math. Probl. Eng.*, vol. 2020, p. 2439265, 2020.

[11]

J. Zhang and Z. Liu, An oracle strongly polynomial algorithm for bottleneck expansion problems, *Optim. Methods Softw.*, vol. 17, no. 1, pp. 61–75, 2002.

[12]

S. Wang, Q. Meng, and H. Yang, Global optimization methods for the discrete network design problem, *Transp. Res. Part B: Meth.*, vol. 50, pp. 42–60, 2013.

[13]

N. Megiddo, Combinatorial optimization with rational objective functions, *Math. Oper. Res.*, vol. 4, no. 4, pp. 414–424, 1979.

Publication history

Copyright

Rights and permissions

Received: 01 January 2023

Revised: 25 April 2023

Accepted: 26 May 2023

Published:
04 December 2023

Issue date: June 2024

© The Author(s) 2024.

The articles published in this open access journal are distributed under the terms of theCreative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/).