TAILIEUCHUNG - Weakly and strongly polynomial algorithms for computing the maximum decrease in uniform arc capacities

In this paper, a new problem on a directed network is presented. Let D be a feasible network such that all arc capacities are equal to U. Given a τ > 0, the network D with arc capacities U − τ is called the τ-network. The goal of the problem is to compute the largest τ such that the τ-network is feasible. | Yugoslav Journal of Operations Research 26 (2016), Number 2, 159–171 DOI: WEAKLY AND STRONGLY POLYNOMIAL ALGORITHMS FOR COMPUTING THE MAXIMUM DECREASE IN UNIFORM ARC CAPACITIES Mehdi GHIYASVAND Department of Mathematics, Faculty of Science, Bu-Ali Sina University, Hamedan, Iran mghiyasvand@ Received: December 2014 / Accepted: May 2015 Abstract: In this paper, a new problem on a directed network is presented. Let D be a feasible network such that all arc capacities are equal to U. Given a τ > 0, the network D with arc capacities U − τ is called the τ-network. The goal of the problem is to compute the largest τ such that the τ-network is feasible. First, we present a weakly polynomial time algorithm to solve this problem, which runs in O(log(nU)) maximum flow computations, where n is the number of nodes. Then, an O(m2 n) time approach is presented, where m is the number of arcs. Both weakly and strongly polynomial algorithms are inspired by McCormick and Ervolina(1994). Keywords: Optimal Witness, Feasible Flow, Maximum Flow. MSC: 90B18. 1. INTRODUCTION A directed network D = (N, A) is given, where N is a set of nodes and A is a set of ordered pairs of nodes, called arcs. We denote an arc from node i to node j by (i, j) and define the flow on arc (i, j) by xij . Let di be the demand at node i (if di 0, we define the network D with arc capacities U − τ as the τ-network. In this paper, we compute the value τ∗ , which is the largest value of τ, such that the τ-network is feasible. Thus, τ∗ is the maximum decrease in all arc capacities such that the new network is still feasible (we call this problem the MDUAC-problem). In this paper, we present weakly and strongly polynomial time algorithms to solve this problem. These algorithms are inspired by McCormick and Ervolina[10]. The most vital arc problem[2,3,4,5,6,8,9,11,12,14,15] is defined for the shortest path and maximum flow problems. In the shortest path problem, the most vital arc is

• Toán học
• Optimal witness
• Feasible flow
• Maximum flow
• Feasible network
• Arc capacities U − τ