A combinatorial arc tolerance analysis for network flow problems. Issue 2 (25th July 2005)

• Record Type: Journal Article
• Authors: Sokkalingam, P. T.; Sharma, Prabha
• Is Part Of: Journal of applied mathematics & decision sciences. Volume 2005:Issue 2(2005)
• Page Start: 83
• Page End: 94
• Publication Date: 2005-07-25
• Subjects: Operations research -- Periodicals; Mathematical models -- Periodicals; Statistics -- Periodicals; Quality control -- Periodicals; Mathematical models; Operations research; Quality control; Statistics; Periodicals; 519.05
• DOI: 10.1155/JAMDS.2005.83
• Languages: English
• ISSNs: 1173-9126

Abstract

Abstract : For the separable convex cost flow problem, we consider the problem of determining tolerance set for each arc cost function. For a given optimal flowx, a valid perturbation ofc i j ( x ) is a convex function that can be substituted forc i j ( x ) in the total cost function without violating the optimality ofx . Tolerance set for ana r c ( i, j ) is the collection of all valid perturbations ofc i j ( x ) . We characterize the tolerance set for eacha r c ( i, j ) in terms of nonsingleton shortest distances between nodesi andj . We also give an efficient algorithm to compute the nonsingleton shortest distances between all pairs of nodes inO ( n 3 ) time wheren denotes the number of nodes in the given graph.