EPSILON-OPTIMALITY FOR BICRITERIA PROGRAMS AND ITS APPLICATION TO MINIMUM COST FLOWS

被引：33

作者：

RUHE, G ^{[1
]}

FRUHWIRTH, B ^{[1
]}

机构：

[1] GRAZ TECH UNIV,INST MATH B,A-8010 GRAZ,AUSTRIA

来源：

COMPUTING | 1990年 / 44卷 / 01期

关键词：

ε-optimality; AMS Subject Classifications: 90B50; 90C35; 65K05; approximation algorithms; Multicriteria programming; network flows;

D O I：

10.1007/BF02247962

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

A subset S⊂X of feasible solutions of a multicriteria optimization problem is called ε-optimal w.r.t. a vector-valued function f:X→Y {Mathematical expression}ℝK if for all x∈X there is a solution zx∈S so that fk(zx)≤(1+ε)fk(x) for all k=1,..., K. For a given accuracy ε>0, a pseudopolynomial approximation algorithm for bicriteria linear programming using the lower and upper approximation of the optimal value function is given. Numerical results for the bicriteria minimum cost flow problem on NETGEN-generated examples are presented. © 1990 Springer-Verlag.

引用

页码：21 / 34

页数：14

共 10 条

[1]

Bertsekas D. P., 1988, Annals of Operations Research, V13, P125, DOI 10.1007/BF02288322

[2]

Blaschke W, 1954, ANAL GEOMETRIE

[3]

BURKARD RE, 1987, 891987 TU GRAZ I MAT

[4] APPROXIMATION OF CONVEX CURVES WITH APPLICATION TO THE BICRITERIAL MINIMUM COST FLOW PROBLEM [J].

FRUHWIRTH, B ;

BURKARD, RE ;

ROTE, G .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1989, 42 (03) :326-338

[5]

GRIGORIADIS MD, 1986, MATH PROGRAM STUD, V26, P83, DOI 10.1007/BFb0121089

[6] NETGEN - PROGRAM FOR GENERATING LARGE-SCALE CAPACITATED ASSIGNMENT, TRANSPORTATION, AND MINIMUM COST FLOW NETWORK PROBLEMS [J].

KLINGMAN, D ;

NAPIER, A ;

STUTZ, J .

MANAGEMENT SCIENCE SERIES A-THEORY, 1974, 20 (05) :814-821

[7]

ORLIN JB, 1988, 20TH P ACM S THEOR C, P377

[8]

ROTE G, 1989, 1181988 TU GRAZ I MA

[9]

Ruhe G., 1988, ZOR, Methods and Models of Operations Research, V32, P9, DOI 10.1007/BF01920568

[10]

RUHE G, 1988, THESIS TH LEIPZIG

← 1 →