A simple polynomial-time rescaling algorithm for solving linear programs
成果类型：
Article
署名作者：
Dunagan, John; Vempala, Santosh
署名单位：
Massachusetts Institute of Technology (MIT); Microsoft
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-007-0095-7
发表日期：
2008
页码：
101-114
关键词：
摘要：
The perceptron algorithm, developed mainly in the machine learning literature, is a simple greedy method for finding a feasible solution to a linear program (alternatively, for learning a threshold function). In spite of its exponential worst-case complexity, it is often quite useful, in part due to its noise-tolerance and also its overall simplicity. In this paper, we show that a randomized version of the perceptron algorithm along with periodic rescaling runs in polynomial-time. The resulting algorithm for linear programming has an elementary description and analysis.