Incremental Network Optimization: Theory and Algorithms
成果类型：
Article
署名作者：
Seref, Onur; Ahuja, Ravindra K.; Orlin, James B.
署名单位：
Virginia Polytechnic Institute & State University; State University System of Florida; University of Florida; Massachusetts Institute of Technology (MIT)
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.1080.0607
发表日期：
2009
页码：
586-594
关键词：
摘要：
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.