An Improved Deterministic Rescaling for Linear Programming Algorithms
An Improved Deterministic Rescaling for Linear Programming Algorithms
复制标题
线性规划算法的改进确定性重标度
DOI：
10.1007/978-3-319-59250-3_22
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
T. Rothvoss
中科院分区：
文献类型：
--
作者：
R. Hoberg;T. Rothvoss
自1950年代以来，由机器学习引起的线性编程的感知算法一直存在。虽然不是多项式时间算法，但由于其简单性和鲁棒性，它在实践中很有用。 2004年，邓纳根（Dunagan）和维格帕拉（Vempala）表明，随机恢复将感知方法转化为多项式时间算法，后来佩纳（Pena）和Soheili进行了确定性的重新确定。在本文中，我们为感知算法提供了确定性的重新缩放，该算法通过使以前的重新恢复方法改善了较早的重新生命。这导致了重新缩放的感知算法的运行时间更快。我们还将证明，相同的重新缩放方法基于乘法权重更新方法产生多项式时间算法。这吸引了与一个最近在理论计算机科学上关注的领域的联系。
The perceptron algorithm for linear programming, arising from machine learning, has been around since the 1950s. While not a polynomial-time algorithm, it is useful in practice due to its simplicity and robustness. In 2004, Dunagan and Vempala showed that a randomized rescaling turns the perceptron method into a polynomial time algorithm, and later Pena and Soheili gave a deterministic rescaling. In this paper, we give a deterministic rescaling for the perceptron algorithm that improves upon the previous rescaling methods by making it possible to rescale much earlier. This results in a faster running time for the rescaled perceptron algorithm. We will also demonstrate that the same rescaling methods yield a polynomial time algorithm based on the multiplicative weights update method. This draws a connection to an area that has received a lot of recent attention in theoretical computer science.
影响因子：
2.7
作者：
Chubanov, Sergei
通讯作者：
Chubanov, Sergei