This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Seref, O. Articles by Orlin, J. B. Search for Related Content

Incremental Network Optimization: Theory and Algorithms

Onur eref, Ravindra K. Ahuja, James B. Orlin

Department of Business Information Technology, Virginia Polytechnic Institute and State University, Blacksburg, Virginia 24061
Department of Industrial and Systems Engineering, University of Florida, Gainesville, Florida 32611
Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
seref{at}vt.edu
ahuja{at}ufl.edu
jorlin{at}mit.edu

In an incremental optimization problem, we are given a feasible solution x⁰ of an optimization problem P, and we want to make an incremental change in x⁰ 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.

Subject classifications: theory; distance algorithms; flow algorithms.
History: Received March 2007; accepted January 2008.