Incremental Network Optimization: Theory and Algorithms

Onur Şeref (), Ravindra K. Ahuja () and James B. Orlin ()
Additional contact information
Onur Şeref: Department of Business Information Technology, Virginia Polytechnic Institute and State University, Blacksburg, Virginia 24061
Ravindra K. Ahuja: Department of Industrial and Systems Engineering, University of Florida, Gainesville, Florida 32611
James B. Orlin: Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139

Operations Research, 2009, vol. 57, issue 3, 586-594

Abstract: In an incremental optimization problem, we are given a feasible solution x 0 of an optimization problem P , and we want to make an incremental change in x 0 that will result in the greatest improvement in the objective function. In this paper, we study the incremental optimization versions of six well-known network problems. We present a strongly polynomial algorithm for the incremental minimum spanning tree problem. We show that the incremental minimum cost flow problem and the incremental maximum flow problem can be solved in polynomial time using Lagrangian relaxation. We consider two versions of the incremental minimum shortest path problem, where increments are measured via arc inclusions and arc exclusions. We present a strongly polynomial time solution for the arc inclusion version and show that the arc exclusion version is NP-complete. We show that the incremental minimum cut problem is NP-complete and that the incremental minimum assignment problem reduces to the minimum exact matching problem, for which a randomized polynomial time algorithm is known.

Keywords: theory; distance algorithms; flow algorithms (search for similar items in EconPapers)
Date: 2009
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1080.0607 (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:57:y:2009:i:3:p:586-594

Access Statistics for this article

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