Paper Info
Title
A modified layered-step interior-point algorithm for linear programming
Abstract
The layered-step interior-point algorithm was introduced by Vavasis and Ye. The algorithm accelerates the path following interior-point algorithm and its arithmetic complexity depends only on the coefficient matrixA. The main drawback of the algorithm is the use of an unknown big constant\(\bar \chi _A \) in computing the search direction and to initiate the algorithm. We propose a modified layered-step interior-point algorithm which does not use the big constant in computing the search direction. The constant is required only for initialization when a well-centered feasible solution is not available, and it is not required if an upper bound on the norm of a primal—dual optimal solution is known in advance. The complexity of the simplified algorithm is the same as that of Vavasis and Ye. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
Year
DOI
Venue
1998
10.1007/BF01580074
Math. Program.
Keywords
Field
DocType
Linear programming, Layered-step interior-point method, Path of centers, Crossover events
Mathematical optimization,Ramer–Douglas–Peucker algorithm,Algorithm complexity,Upper and lower bounds,Algorithm,Path following,Linear programming,Initialization,Interior point method,Mathematics
Journal
Volume
Issue
ISSN
82
3
1436-4646
Citations 
PageRank 
References 
14
1.45
8
Authors
3
Name
Order
Citations
PageRank
Nimrod Megiddo14244668.46
Shinji Mizuno2792153.37
Takashi Tsuchiya3182.02