Random Walks on Polytopes and an Affine Interior Point Method for Linear Programming

被引：39

作者：

Kannan, Ravindran ^{[1
]}

Narayanan, Hariharan ^{[2
]}

机构：

[1] Microsoft Res Labs, Algorithms Res Grp, Bangalore 560080, Karnataka, India

[2] Univ Chicago, Dept Comp Sci, Chicago, IL 60637 USA

来源：

MATHEMATICS OF OPERATIONS RESEARCH | 2012年 / 37卷 / 01期

关键词：

random walks; polytopes; interior point methods; POLYNOMIAL-TIME ALGORITHM; HIT-AND-RUN; LOGCONCAVE FUNCTIONS; VOLUME ALGORITHM; CONVEX-BODIES;

D O I：

10.1287/moor.1110.0519

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

Let K be a polytope in R-n defined by m linear inequalities. We give a new Markov chain algorithm to draw a nearly uniform sample from K. The underlying Markov chain is the first to have a mixing time that is strongly polynomial when started from a "central" point. We use this result to design an affine interior point algorithm that does a single random walk to solve linear programs approximately.

引用

页码：1 / 20

页数：20

共 24 条

[1]

Abernethy J., 2008, 21 ANN C LEARN THEOR, P263

[2] THE COMPLEXITY OF PARTIAL DERIVATIVES [J].

BAUR, W ;

STRASSEN, V .

THEORETICAL COMPUTER SCIENCE, 1983, 22 (03) :317-330

[3] Projective re-normalization for improving the behavior of a homogeneous conic linear system [J].

Belloni, Alexandre ;

Freund, Robert M. .

MATHEMATICAL PROGRAMMING, 2009, 118 (02) :279-299

[4]

DIACONIS P, 1985, ANN STAT, V13, P845, DOI 10.1214/aos/1176349634

[5]

Dikin I.I., 1967, Soviet Mathematics Doklady, V8, P674

[6] A RANDOM POLYNOMIAL-TIME ALGORITHM FOR APPROXIMATING THE VOLUME OF CONVEX-BODIES [J].

DYER, M ;

FRIEZE, A ;

KANNAN, R .

JOURNAL OF THE ACM, 1991, 38 (01) :1-17

[7]

Kannan R, 1997, RANDOM STRUCT ALGOR, V11, P1, DOI 10.1002/(SICI)1098-2418(199708)11:1<1::AID-RSA1>3.0.CO

[8]

2-X

[9]

Kannan Ravi, 1997, STOC '97, P696

[10] A NEW POLYNOMIAL-TIME ALGORITHM FOR LINEAR-PROGRAMMING [J].

KARMARKAR, N .

COMBINATORICA, 1984, 4 (04) :373-395

← 1 2 3 →