A RANDOMIZED ALGORITHM FOR FIXED-DIMENSIONAL LINEAR-PROGRAMMING

被引：28

作者：

DYER, ME

FRIEZE, AM

机构：

[1] CARNEGIE MELLON UNIV,PITTSBURGH,PA 15213

[2] UNIV LONDON QUEEN MARY COLL,LONDON E1 4NS,ENGLAND

来源：

MATHEMATICAL PROGRAMMING | 1989年 / 44卷 / 02期

关键词：

D O I：

10.1007/BF01587088

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

引用

页码：203 / 212

页数：10

共 9 条

[1] NEW APPLICATIONS OF RANDOM SAMPLING IN COMPUTATIONAL GEOMETRY [J].

CLARKSON, KL .

DISCRETE & COMPUTATIONAL GEOMETRY, 1987, 2 (02) :195-222

[2] LINEAR-PROGRAMMING IN O(NX3D2) TIME [J].

CLARKSON, KL .

INFORMATION PROCESSING LETTERS, 1986, 22 (01) :21-24

[3] LINEAR TIME ALGORITHMS FOR 2-VARIABLE AND 3-VARIABLE LINEAR-PROGRAMS [J].

DYER, ME .

SIAM JOURNAL ON COMPUTING, 1984, 13 (01) :31-45

[4] ON A MULTIDIMENSIONAL SEARCH TECHNIQUE AND ITS APPLICATION TO THE EUCLIDEAN ONE-CENTER PROBLEM [J].

DYER, ME .

SIAM JOURNAL ON COMPUTING, 1986, 15 (03) :725-738

[5] EPSILON-NETS AND SIMPLEX RANGE QUERIES [J].

HAUSSLER, D ;

WELZL, E .

DISCRETE & COMPUTATIONAL GEOMETRY, 1987, 2 (02) :127-151

[6] PROBABILITY-INEQUALITIES FOR SUMS OF BOUNDED RANDOM-VARIABLES [J].

HOEFFDING, W .

JOURNAL OF THE AMERICAN STATISTICAL ASSOCIATION, 1963, 58 (301) :13-+

[7] LINEAR-TIME ALGORITHMS FOR LINEAR-PROGRAMMING IN R3 AND RELATED PROBLEMS [J].

MEGIDDO, N .

SIAM JOURNAL ON COMPUTING, 1983, 12 (04) :759-776

[8] LINEAR-PROGRAMMING IN LINEAR TIME WHEN THE DIMENSION IS FIXED [J].

MEGIDDO, N .

JOURNAL OF THE ACM, 1984, 31 (01) :114-127

[9]

Schrijver A., 1986, THEORY LINEAR INTEGE

← 1 →