Solving Inverse Spanning Tree Problems Through Network Flow Techniques

P. T. Sokkalingam, Ravindra K. Ahuja and James B. Orlin
Additional contact information
P. T. Sokkalingam: HCL-CISCO ODC Centre, Chennai, India
Ravindra K. Ahuja: University of Florida, Gainesville, Florida
James B. Orlin: Massachusetts Institute of Technology, Cambridge, Massachusetts

Operations Research, 1999, vol. 47, issue 2, 291-298

Abstract: Given a solution x * and an a priori estimated cost vector c , the inverse optimization problem is to identify another cost vector d so that x * is optimal with respect to the cost vector d and its deviation from c is minimum. In this paper, we consider the inverse spanning tree problem on an undirected graph G = ( N , A ) with n nodes and m arcs, and where the deviation between c and d is defined by the rectilinear distance between the two vectors, that is, L 1 norm. We show that the inverse spanning tree problem can be formulated as the dual of an assignment problem on a bipartite network G 0 = ( N 0 , A 0 ) with N 0 = N 1 ∪ N 2 and A 0 ⊆ N 1 × N 2 . The bipartite network satisfies the property that | N 1 | = ( n − 1), | N 2 | = ( m − n + 1), and | A 0 | = O ( nm ). In general, | N 1 | ≪ | N 2 |. Using this special structure of the assignment problem, we develop a specific implementation of the successive shortest path algorithm that runs in O ( n 3 ) time. We also consider the weighted version of the inverse spanning tree problem in which the objective function is to minimize the sum of the weighted deviations of arcs. The weighted inverse spanning tree can be formulated as the dual of the transportation problem. Using a cost scaling algorithm, this transportation problem can be solved in O ( n 2 m log( nC )) time, where C denotes the largest arc cost in the data. Finally, we consider a minimax version of the inverse spanning tree problem and show that it can be solved in O ( n 2 ) time.

Keywords: networks/graphs; flow algorithms; minimum cost flow problem; networks/graphs; tree algorithms; inverse spanning tree problem; programming; linear; application of duality theory (search for similar items in EconPapers)
Date: 1999
References: View complete reference list from CitEc
Citations: View citations in EconPapers (19)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.47.2.291 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:47:y:1999:i:2:p:291-298

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().