• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>IEEE Annual Symposium on Foundations of Computer Science >Path Finding Methods for Linear Programming: Solving Linear Programs in Õ(vrank) Iterations and Faster Algorithms for Maximum Flow
【24h】

Path Finding Methods for Linear Programming: Solving Linear Programs in Õ(vrank) Iterations and Faster Algorithms for Maximum Flow

机译：线性规划的路径查找方法：以Õ（vrank）迭代求解线性程序和更快的最大流量算法

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

In this paper, we present a new algorithm for solving linear programsthat requires only Õ(√rank(A)L) iterationswhere A is the constraint matrix of a linear program with mconstraints, n variables, and bit complexity L. Each iterationof our method consists of solving Õ(1) linear systems andadditional nearly linear time computation. Our method improves uponthe previous best iteration bounds by factor of Ω(m/rank(A))1/4 for methods with polynomial time computable iterations and by Ω((m/rank(A))1/2) for methods which solve at most Õ(1) linear systems ineach iteration each achieved over 20 years ago.Applying our techniques to the linear program formulation of maximumflow yields an Õ(|E| √(|V|) log2(U)) time algorithm forsolving the maximum flow problem on directed graphs with |E| edges,|V| vertices, and capacity ratio U. This improves upon the previousfastest running time of O(|E| min(|E|(1/2), |V|(2/3)) log(|V|2/|E|) log(U))achieved over 15 years ago by Goldberg and Rao and improves upon theprevious best running times for solving dense directed unit capacitygraphs of O(|E| min(|E|(1/2), |V|(2/3))) achieved by Even and Tarjanover 35 years ago and a running time of Õ(|E|(10/7)) achievedrecently by Mądry.
机译：在本文中，我们提出了一种仅需Õ（√rank（A）L）次迭代即可求解线性程序的新算法，其中A是具有m个约束，n个变量和位复杂度L的线性程序的约束矩阵。 Õ（1）线性系统的求解和附加的近似线性时间计算。对于具有多项式时间可计算迭代的方法，我们的方法将先前的最佳迭代边界提高了Ω（m / rank（A））1/4，对于求解的方法则提高了Ω（（m / rank（A））1/2）每次迭代最多最多可在20年前实现Õ（1）个线性系统。将我们的技术应用到最大流量的线性程序公式化中，将产生Õ（| E |√（| V |）log2（U））时间算法来求解| E |有向图上的流问题边，| V |顶点和容量比U。这比以前最快的运行时间O（| E | min（| E |（1/2），| V |（2/3））log（| V | 2 / | E | ）log（U））于15年前由Goldberg和Rao实现，并改进了以前的最佳运行时间，用于求解O（| E | min（| E |（1/2），| V |（2 / 3）））于35年前由Even和Tarjanover实现，最近由Mądry实现了Õ（| E |（10/7））的运行时间。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号