ON THE COMPLEXITY OF APPROXIMATING THE MAXIMAL INSCRIBED ELLIPSOID FOR A POLYTOPE

被引：87

作者：

KHACHIYAN, LG

TODD, MJ

机构：

[1] CORNELL UNIV,SCH OPERAT RES & IND ENGN,E&TC BLDG,ITHACA,NY 14853

[2] RUTGERS UNIV,DEPT COMP SCI,NEW BRUNSWICK,NJ 08903

[3] RUSSIAN ACAD SCI,CTR COMP,MOSCOW,RUSSIA

来源：

MATHEMATICAL PROGRAMMING | 1993年 / 61卷 / 02期

关键词：

MAXIMAL INSCRIBED ELLIPSOID; MAXIMAL INSCRIBED PARABOLOID; PATH-FOLLOWING NEWTON METHOD; COMPUTATIONAL COMPLEXITY;

D O I：

10.1007/BF01582144

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We give a new polynomial bound on the complexity of approximating the maximal inscribed ellipsoid for a polytope.

引用

页码：137 / 159

页数：23

共 14 条

[1] AN ALGORITHM FOR SEPARATING PATTERNS BY ELLIPSOIDS [J].

BARNES, ER .

IBM JOURNAL OF RESEARCH AND DEVELOPMENT, 1982, 26 (06) :759-764

[2]

Beckenbach E. F., 1961, INEQUALITIES

[3]

Danzer L., 1957, ARCH MATH, V8, P214

[4] ON THE COMPLEXITY OF 4 POLYHEDRAL SET CONTAINMENT PROBLEMS [J].

FREUND, RM ;

ORLIN, JB .

MATHEMATICAL PROGRAMMING, 1985, 33 (02) :139-145

[5]

GOFFIN JL, 1988, TRENDS MATH OPTIMIZA, V84, P79

[6]

John F., 1948, STUDIES ESSAYS PRESE, P187, DOI DOI 10.1007/978-3-0348-0439-4_9

[7]

NESTEROV JE, 1989, SELF CONCORDANT FUNC

[8] A POLYNOMIAL-TIME ALGORITHM, BASED ON NEWTON METHOD, FOR LINEAR-PROGRAMMING [J].

RENEGAR, J .

MATHEMATICAL PROGRAMMING, 1988, 40 (01) :59-93

[9]

SONNEVEND G, 1988, ISNM, V84, P311

[10]

Tarasov S., 1988, SOVIET MATH DOKLADY, V37, P226

← 1 2 →