Blog
About

0
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      A Deterministic Linear Program Solver in Current Matrix Multiplication Time

      Preprint

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          Interior point algorithms for solving linear programs have been studied extensively for a long time [e.g. Karmarkar 1984; Lee, Sidford FOCS'14; Cohen, Lee, Song STOC'19]. For linear programs of the form \(\min_{Ax=b, x \ge 0} c^\top x\) with \(n\) variables and \(d\) constraints, the generic case \(d = \Omega(n)\) has recently been settled by Cohen, Lee and Song [STOC'19]. Their algorithm can solve linear programs in \(\tilde O(n^\omega \log(n/\delta))\) expected time, where \(\delta\) is the relative accuracy. This is essentially optimal as all known linear system solvers require up to \(O(n^{\omega})\) time for solving \(Ax = b\). However, for the case of deterministic solvers, the best upper bound is Vaidya's 30 years old \(O(n^{2.5} \log(n/\delta))\) bound [FOCS'89]. In this paper we show that one can also settle the deterministic setting by derandomizing Cohen et al.'s \(\tilde{O}(n^\omega \log(n/\delta))\) time algorithm. This allows for a strict \(\tilde{O}(n^\omega \log(n/\delta))\) time bound, instead of an expected one, and a simplified analysis, reducing the length of their proof of their central path method by roughly half. Derandomizing this algorithm was also an open question asked in Song's PhD Thesis. The main tool to achieve our result is a new data-structure that can maintain the solution to a linear system in subquadratic time. More accurately we are able to maintain \(\sqrt{U}A^\top(AUA^\top)^{-1}A\sqrt{U}\:v\) in subquadratic time under \(\ell_2\) multiplicative changes to the diagonal matrix \(U\) and the vector \(v\). This type of change is common for interior point algorithms. Previous algorithms [e.g. Vaidya STOC'89; Lee, Sidford FOCS'15; Cohen, Lee, Song STOC'19] required \(\Omega(n^2)\) time for this task. [...]

          Related collections

          Most cited references 3

          • Record: found
          • Abstract: not found
          • Article: not found

          A polynomial-time algorithm, based on Newton's method, for linear programming

           James Renegar (1988)
            Bookmark
            • Record: found
            • Abstract: not found
            • Article: not found

            Self-Scaled Barriers and Interior-Point Methods for Convex Programming

              Bookmark
              • Record: found
              • Abstract: not found
              • Article: not found

              An optimal minimum spanning tree algorithm

                Bookmark

                Author and article information

                Journal
                25 October 2019
                Article
                1910.11957

                http://arxiv.org/licenses/nonexclusive-distrib/1.0/

                Custom metadata
                To appear in SODA'20
                cs.DS

                Data structures & Algorithms

                Comments

                Comment on this article