ABOUT STRONGLY POLYNOMIAL-TIME ALGORITHMS FOR QUADRATIC OPTIMIZATION OVER SUBMODULAR CONSTRAINTS

被引：60

作者：

HOCHBAUM, DS ^{[1
]}

HONG, SP ^{[1
]}

机构：

[1] UNIV CALIF BERKELEY,DEPT IND ENGN & OPERAT RES,BERKELEY,CA 94720

来源：

MATHEMATICAL PROGRAMMING | 1995年 / 69卷 / 02期

关键词：

QUADRATIC PROGRAMMING; SUBMODULAR CONSTRAINTS; KUHN-TUCKER CONDITIONS; LEXICOGRAPHICALLY OPTIMAL FLOW; PARAMETRIC MAXIMUM FLOW;

D O I：

10.1007/BF01585561

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We present new strongly polynomial algorithms for special cases of convex separable quadratic minimization over submodular constraints. The main results are: an O(NM log(N-2/M)) algorithm for the problem Network defined on a network on M arcs and N nodes; an O(n log n) algorithm for the tree problem on n variables; an O(n log n) algorithm for the Nested problem, and a linear time algorithm for the Generalized Upper Bound problem. These algorithms are the best known so far for these problems. The status of the general problem and open questions are presented as well.

引用

页码：269 / 309

页数：41

共 25 条

[1] EFFICIENT INTEGER OPTIMIZATION ALGORITHMS FOR OPTIMAL COORDINATION OF CAPACITORS AND REGULATORS [J].

BALDICK, R ;

WU, FF .

IEEE TRANSACTIONS ON POWER SYSTEMS, 1990, 5 (03) :805-812

[2]

BEST MJ, 1990, CORR9004 U WAT DEP C

[3]

BLUM M, 1972, J COMPUT SYST SCI, V7, P448

[4] AN O(N) ALGORITHM FOR QUADRATIC KNAPSACK-PROBLEMS [J].

BRUCKER, P .

OPERATIONS RESEARCH LETTERS, 1984, 3 (03) :163-166

[5] SENSITIVITY THEOREMS IN INTEGER LINEAR-PROGRAMMING [J].

COOK, W ;

GERARDS, AMH ;

SCHRIJVER, A ;

TARDOS, E .

MATHEMATICAL PROGRAMMING, 1986, 34 (03) :251-264

[6] STRONGLY POLYNOMIAL ALGORITHMS FOR THE QUADRATIC TRANSPORTATION PROBLEM WITH A FIXED NUMBER OF SOURCES [J].

COSARES, S ;

HOCHBAUM, DS .

MATHEMATICS OF OPERATIONS RESEARCH, 1994, 19 (01) :94-111

[7] ON AN OPTIMIZATION PROBLEM WITH NESTED CONSTRAINTS [J].

DYER, ME ;

FRIEZE, AM .

DISCRETE APPLIED MATHEMATICS, 1990, 26 (2-3) :159-173

[8] THE COMPLEXITY OF SELECTION AND RANKING IN X + Y AND MATRICES WITH SORTED COLUMNS [J].

FREDERICKSON, GN ;

JOHNSON, DB .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1982, 24 (02) :197-208

[9] LEXICOGRAPHICALLY OPTIMAL BASE OF A POLYMATROID WITH RESPECT TO A WEIGHT VECTOR [J].

FUJISHIGE, S .

MATHEMATICS OF OPERATIONS RESEARCH, 1980, 5 (02) :186-196

[10]

Fujishige S., 1991, ANN DISCRETE MATH, V47

← 1 2 3 →