betaFeedback

WorksMathematics

Solving Classes of Linear Programs with Strongly Polynomial Straight Line Complexity in Strongly Polynomial Time

Abstract

Recently, Allamigeon, Dadush, Loho, Natura, and Végh (ADLNV, SICOMP 2025) introduced an interior point method for linear programs whose number of iterations is bounded by the so-called straight line complexity (SLC) of the instance. This yields a strongly polynomial bound on the number of iterations of the corresponding interior point algorithm for broad classes of linear programs. In particular, in the companion paper we give a strongly polynomial straight line complexity bound for two-variable-per-inequality linear programs. However, in order to obtain a strongly polynomial algorithm for these classes, one also needs to address two important technical issues: initialization and bit-complexity bounds. Standard IPM initialization techniques either require numerical estimates that cannot be obtained in the strongly polynomial model, or involve modifying the instance in ways that do not preserve the geometry of the original LP, potentially affecting the SLC. In this work, we present an initialization framework for interior point methods for linear programming, along with a rounding procedure that ensures the continued feasibility of the IPM. We develop a multistage scheme in which each stage can be initialized in strongly polynomial time given the output of the previous stage. Additionally, we address the challenge of controlling the bit complexity of each iterate throughout the algorithm. To this end, we show that it is possible to represent iterates as low-complexity convex combinations of vertices and extreme rays. Our combinatorial rounding step is independent of the algorithm in ADLNV 2025, and can be applied more broadly in the context of path-following methods.

Introduction

We consider linear programming (LP) in the following primal-dual form:

min⁡⟨c,x⟩max⁡⟨b,y⟩Ax=bATy+s=cx≥0ns≥0n\begin{aligned} \min\quad&\langle c,x\rangle& \max\quad&\langle b,y\rangle\\ &Ax=b && A^{\mathsf T}y+s=c\\ &x\ge0_n && s\ge0_n \end{aligned}

(LP(A,b,c)(A,b,c))

where A∈Rm×nA\in\mathbb{R}^{m\times n}, b∈Rmb\in\mathbb{R}^{m}, c∈Rnc\in\mathbb{R}^{n}, and AA has rank mm. Our focus is on LP algorithms that find exact primal and dual optimal solutions, or conclude infeasibility or unboundedness.

The first polynomial-time LP algorithms were the ellipsoid method by Khachiyan in 1979 [28] and interior point methods, introduced by Karmarkar in 1984 [27]. However, it remains an outstanding open question to find a strongly polynomial algorithm for linear programming. The question was listed by the Fields medalist Smale as one of the most prominent mathematical challenges for the 21st century [Sma98]. In such an algorithm, only poly⁡(n)\operatorname{poly}(n) basic arithmetic operations and comparisons are allowed, and the algorithm uses polynomial space (see § 1.1 for formal definitions).

The notion of strongly polynomial algorithms was first formally introduced by Megiddo [31], under the term ‘genuinely polynomial’; he gave such an algorithm for finding feasible solutions to two-variable-per-inequality (2VPI) linear programs. In a seminal, Fulkerson-prize winning paper [Tar85], Tardos obtained the first strongly polynomial algorithm for minimum-cost circulations. A particularly important technique in this paper was variable fixing: by solving an approximate version of the LP with rounded costs, one can deduce that a certain variable is at the lower or upper capacity bound in an optimal solution. Towards general LP, Tardos [Tar86] extended this approach to obtain a strongly polynomial algorithm for ‘combinatorial LPs’. More precisely, for LP⁡(A,b,c)\operatorname{LP}(A,b,c) with an integer constraint matrix A∈Zm×nA\in\mathbb{Z}^{m\times n}, this algorithm runs in poly⁡(n,log⁡ΔA)\operatorname{poly}(n,\log\Delta_A) iterations, where ΔA\Delta_A is the maximum absolute value of a subdeterminant of AA. The running time is independent of bb and cc. In particular, this bound is strongly polynomial if all entries of AA are at most poly⁡(n)\operatorname{poly}(n), such as for multicommodity flows and other combinatorial problems.

Strongly polynomial algorithms from interior point methods. Interior point methods (IPMs) give the fastest current weakly polynomial algorithms for general LPs, see [12, 7, 5, 26], and for special classes such as minimum-cost circulations [11, 4] and multicommodity flows [9]. Somewhat surprisingly, they are also a potent approach in the context of strongly polynomial computability. In recent years, IPMs have emerged as a unifying tool in this context.

The algorithms discussed next fall into the class of primal-dual path-following algorithms. A key concept here is the central path, the algebraic curve formed by minimizers of ⟨c,x⟩−μ∑i=1nlog⁡(xi)\langle c,x\rangle-\mu\sum_{i=1}^{n}\log(x_i) over the domain {x:Ax=b}\{x:Ax=b\} for μ>0\mu>0 (see § 1.2 for more details). As μ→0\mu\to0, the limit of the central path is an optimal solution. Path-following methods maintain iterates in a certain neighborhood of the central path while geometrically decreasing μ\mu and thus the optimality gap. The logarithmic barrier function above can be replaced by more general barrier functions.

The main progress measure in IPMs is the decrease in optimality gap and thus these methods are inherently weakly polynomial; finding an exact optimal solution typically requires an additional rounding step. In the influential paper [VY96], Vavasis and Ye introduced Layered Least Squares (LLS) IPMs that terminate with an exact optimal solution in poly⁡(n,log⁡χˉA)\operatorname{poly}(n,\log\bar{\chi}_A) arithmetic operations, where χˉA\bar{\chi}_A is the Dikin–Stewart–Todd condition number of the matrix AA. Remarkably, the number of arithmetic operations is independent of the vectors bb and cc. For integer matrices, χˉA=O(nΔA)\bar{\chi}_A=O(n\Delta_A), so this strengthens Tardos’s result. We note that a similar dependence, obtained via a black-box variable-fixing approach extending Tardos’s work, was established in [18].

This led to a line of research on improved combinatorial IPMs [32, 33, 34, 29]. The paper by Dadush, Huiberts, Natura, and Végh [DHN^24] revealed that χˉA\bar{\chi}_A is closely related to the circuit imbalance measure κA\kappa_A that bounds the maximum absolute value of ratios of two nonzero entries of an elementary vector in the kernel of AA. Moreover, they obtained an LLS algorithm invariant under column rescaling, thus improving the dependence to the best κA∗\kappa_A^* value achievable under column rescalings.

The above results may raise hopes of finding a strongly polynomial IPM. However, the papers by Allamigeon, Benchimol, Gaubert, and Joswig [ABG^18], see also [3 ZLY24], yield a surprising negative answer. By analyzing the tropical limits of linear programs, these papers exhibit parametric families of LPs such that for suitably large parameter values, no path-following method can be strongly polynomial. This was first shown for the standard logarithmic barrier [ABG^18], and later for arbitrary self-concordant barriers [3].

IPMs matching straight line complexity. The lower bounds in [1, 3] are ultimately based on the following insight. The trajectory of any path-following IPM is a piecewise linear curve in the neighborhood of the central path; the number of pieces corresponds to the number of iterations. Thus, a lower bound on the number of linear segments of any piecewise linear curve in the neighborhood provides a lower bound on the number of iterations. The above-mentioned papers exhibit families of LPs with exponential lower bounds.

The recent result by Allamigeon, Dadush, Loho, Natura, and Végh [2] complements these negative results by a positive algorithmic bound. Namely, their Subspace Layered Least Squares (SLLS) IPM matches the straight line complexity lower bound within a strongly polynomial O~(n1.5)\widetilde{O}(n^{1.5}) factor; their result is stated formally in Theorem 1.6. At a high level, the algorithm exploits the structural property that whenever there is a long straight line segment in the neighborhood of the central path, the variables exhibit a ‘polarized’ behavior: There exists a partition [n]=(B,N)[n] = (B, N) such that primal variables barely change on BB and scale roughly with the gap on NN, while the reverse holds for the dual variables. The SLLS IPM can detect such a partition and uses a step that exhibits this behavior to reach a point near the end of such a segment in O~(n1.5)\widetilde{O}(n^{1.5}) steps. Very recently, [17] improved the iteration complexity of the above algorithm, by using a strongly polynomial implementation of the trust region steps introduced in [29]. In particular, they showed that the iteration complexity of the Trust Region IPM is optimal within a constant factor in the ℓ2\ell_2-neighborhood.

The SLLS IPM in [2] provides a unifying framework for strongly polynomially solvable classes of LPs. One can show that the straight line complexity is bounded polynomially by nn and log⁡(κA∗)\log(\kappa_A^*), the optimized circuit imbalance measure, which was the most general previously known parametrization. Another example is the class of discounted Markov Decision Processes [Ye05], and more generally, LPs where the nonzero entries of basic solutions fall into strongly polynomially bounded intervals [10]. It is also the key tool for settling the strongly polynomial complexity of two-variable-per-inequality LPs, as discussed next.

Two-variable-per-inequality LPs. We say that the dual program in LP(A,b,c)LP(A,b,c) is a two-variable-per-inequality (2VPI) linear program if every row of ATA^{\mathsf{T}} includes at most two nonzero entries. In such a case, we refer to the pair of LPs as a 2VPI primal-dual pair.

As already mentioned, one of the first strongly polynomial algorithms in the literature was given by Megiddo [31] for the 2VPI feasibility problem. As shown in [24], 2VPI primal-dual pairs can be strongly polynomially reduced to solving the minimum-cost generalized flow problem, the classical network flow model where the flow may change while traversing the arcs according to gain factors. The strongly polynomial algorithms for generalized flow maximization [Vé17, OV20] thus imply a strongly polynomial algorithm for finding primal-feasible solutions of LPs with at most two nonzeros per column. However, for the minimum-cost generalized flow problem, and for 2VPI primal-dual pairs, this was only settled recently in the conference paper by the authors [15]:

Theorem 1.1. There is a deterministic strongly polynomial algorithm for the minimum-cost generalized flow problem, and for two-variable-per-inequality primal-dual pairs.

A key ingredient in showing Theorem 1.1 is proving strongly polynomial straight-line complexity bounds for minimum-cost generalized flow problems; these bounds are described in the companion paper [16]. However, to obtain the claimed strongly polynomial bound, there are significant additional challenges regarding initialization and implementation in the Turing model. The current paper exhibits general techniques to address these challenges.

Summary of contributions. Our contributions, presented in § 1.4, can be informally summarized as follows:

  1. Initialization: IPMs require a pair of strictly feasible initial primal and dual solutions near the central path, even though a strictly feasible (or even a feasible) solution may not exist. We present a careful initialization scheme that solves linear programs in three stages, and preserves the straight line complexity bounds; see Theorem 1.7.

  1. Implementation in the Turing model: We show that the bit-length of the computations can be controlled in a model using only basic arithmetic operations and comparisons; see Theorem 1.8.

Initialization is always a significant issue when applying IPMs. It is usually done by embedding the LP into an auxiliary system that is strictly feasible for which a suitable starting solution can be easily found and the optimal solutions of the auxiliary LP map to the optimal solutions of the original LP. Such constructions, however, may lose the combinatorial structure of the LP, or rely on numerical estimates based on bit-complexity (see § 1.4.1). In contrast, our initialization scheme does not require any a priori numerical estimates. The overall running time in Theorem 1.7 is bounded by the maximum straight line complexity of the original LP and its three simple modifications. For the min-cost generalized flow problem, each of these LPs also describes a generalized flow instance.

Our second contribution addresses a fundamental issue regarding the computational models; we formally introduce the real RAM and Turing models in § 1.1 below. While ‘combinatorial’ algorithms such as Tardos’s results [Tar85, Tar86] or the 2VPI/generalized flow papers [31 Vég17, 36] are strongly polynomial in the Turing model of computation, the Vavasis–Ye algorithm [VY96] and all subsequent work on combinatorial IPMs, including the SLLS IPM [2], are presented in the real RAM model. Whenever the straight line complexity is strongly polynomially bounded, the number of arithmetic operations is strongly polynomial. However, in the Turing model one needs to ensure that the algorithm only uses polynomial space. The above algorithms are ‘stepwise strongly polynomial’, i.e., each iteration can be implemented in strongly polynomial time. Still, the bit-length could increase exponentially over the sequence of iterations. This notion is defined in § 1.1, where we also discuss why simple rounding techniques are not applicable in the strongly polynomial model.

In Theorem 1.8, we introduce a ‘combinatorial’ strongly polynomial rounding step. This is applicable broadly for the combinatorial IPMs above, and can thus turn them, under certain conditions explained below, into strongly polynomial algorithms in the Turing model for the classes where their iteration complexities are strongly polynomial.

Computational models

We now turn to the discussion of the computational models. There are multiple related, yet distinct notions of a strongly polynomial computational model. Smale’s question was posed in the Blum–Shub–Smale (BSS) real model of computation [8]. In this model, the input can be given by arbitrary real numbers, and one step may compute a rational function of the previously computed quantities with real coefficients, or make comparisons between two quantities. In the more restrictive real RAM model, one can perform a sequence of elementary arithmetic operations (++, −-, ×\times, //) and comparisons (≥\ge) on real numbers. We say that an algorithm is polynomial in the real RAM model if the number of elementary arithmetic operations and comparisons is bounded polynomially in the dimension of the input; in the case of LP, this is K=n×m+n+mK = n \times m + n + m.

We now turn to the Turing model. Consider a problem where the input is given by KK integers; for LP, the input (A,b,c)(A,b,c) is described by K=2(n×m+n+m)K = 2(n \times m + n + m) integers representing the rational entries. An algorithm is strongly polynomial in the Turing model (see [20]), if it only performs poly⁡(K)\operatorname{poly}(K) elementary arithmetic operations and comparisons as in the real RAM model; in the LP case, this means poly⁡(m,n)\operatorname{poly}(m,n) arithmetic operations. Additionally, the bit-complexity of the numbers during the computations must remain polynomially bounded in the encoding length of the input. Equivalently, the algorithm must be polynomial in the real RAM model and also be in PSPACE.

There is an ambiguity in the models regarding how divisions can be implemented; see discussion of variants in [20 Section 1.3]. The results of this paper work with the most restricted setting: all numbers are maintained as numerator–denominator pairs, which are never reduced to lowest terms. To make this precise, we distinguish a rational number from the pair that represents it, and define sizes of numbers following [20].

Definition 1.2 (Encoded rationals and sizes of numbers). For an integer k∈Zk \in\mathbb{Z}, we define the encoding length of kk as size⁡(k)=1+⌈log⁡2(∣k∣+1)⌉\operatorname{size}(k) = 1 + \lceil\log_{2}(|k| + 1) \rceil. We represent rational numbers as ordered pairs of integers, and accordingly set

Q^:=Z×Z>0,val⁡(p,q):=pq,size⁡(p,q):=size⁡(p)+size⁡(q),\widehat{\mathbb{Q}} := \mathbb{Z} \times\mathbb{Z}_{>0}, \qquad\operatorname{val}(p,q) := \frac{p}{q}, \qquad\operatorname{size}(p,q) := \operatorname{size}(p) + \operatorname{size}(q),

calling the elements of Q^\widehat{\mathbb{Q}} encoded rationals. The canonical value map val⁡:Q^→Q\operatorname{val}: \widehat{\mathbb{Q}} \to\mathbb{Q} is surjective, and Q\mathbb{Q} can be seen as the quotient of Q^\widehat{\mathbb{Q}} by the equivalence (p,q)∼(p′,q′)(p,q) \sim(p',q') if and only if pq′=p′qpq' = p'q. We regard an integer kk as the encoded rational (k,1)(k,1), note that its two sizes then differ by the additive constant 22, and we set Q^>0:={(p,q)∈Q^∣p>0}\widehat{\mathbb{Q}}_{>0} := \{(p,q) \in\widehat{\mathbb{Q}} \mid p > 0\}. Further, for a rational vector or matrix, the size is defined as the sum of the sizes of the entries. For matrices and vectors a1,a2,…,aka_1, a_2, \ldots, a_k of possibly different dimensions, we let

size⁡(a1,a2,…,ak)=∑i=1ksize⁡(ai)\operatorname{size}(a_1,a_2,\ldots,a_k)=\sum_{i=1}^{k}\operatorname{size}(a_i). Finally, for a value α∈Q\alpha\in\mathbb{Q} we set

size⁡(α):=min⁡{size⁡(a)∣a∈Q^, val⁡(a)=α},\operatorname{size}(\alpha) := \min\{\operatorname{size}(a) \mid a \in\widehat{\mathbb{Q}},\ \operatorname{val}(a)=\alpha\},

the minimum being attained by the lowest-terms representation, and likewise entrywise for rational vectors and matrices, matching the classical notion of encoding length of a rational number.

Every number produced by our algorithms is an encoded rational. For (p,q),(p′,q′)∈Q^(p,q),(p',q') \in\widehat{\mathbb{Q}} an addition returns (pq′+p′q,qq′)(pq'+p'q,qq'), a multiplication returns (pp′,qq′)(pp',qq'), and a division pq/p′q′\frac{p}{q}/\frac{p'}{q'} returns (pq′,qp′)(pq',qp'), with the sign normalized so that the second coordinate stays positive.

We identify an encoded rational with its value wherever only the value matters: for a∈Q^na \in\widehat{\mathbb{Q}}^n and S⊆QnS \subseteq\mathbb{Q}^n we write a∈Sa \in S for val⁡(a)∈S\operatorname{val}(a) \in S, and equations, inequalities and norms of encoded objects are those of their values.

While a strongly polynomial algorithm in the Turing model implies a polynomial algorithm in the real RAM model, the converse is not necessarily the case: enforcing PSPACE may be challenging. For example, Gaussian elimination needs to be done carefully to keep the sizes of numbers under control, see [19] and [20 Section 1.4].

The LLS interior point methods [VY96, MMT98, MT03, MT05, DHNV24, ADL+25] are polynomial in the real RAM model2 whenever log⁡(χ‾A)=poly⁡(n)\log(\overline{\chi}_{A})=\operatorname{poly}(n). However, we are not aware of any strongly polynomial implementation of such algorithms in the Turing model. The next definition highlights the key difficulty in developing such implementations.

Stepwise strongly polynomial algorithms. By an iterative algorithm we mean an algorithm that computes a sequence of points z(0),z(1),…,z(T)∈Rkz^{(0)},z^{(1)},\ldots,z^{(T)} \in\mathbb{R}^k for some k∈Nk \in\mathbb{N}; interior point methods all have this form. By a stepwise strongly polynomial algorithm we mean an iterative algorithm that, given a rational input z(t)∈Qkz^{(t)} \in\mathbb{Q}^k, computes the next iterate z(t+1)∈Qkz^{(t+1)} \in\mathbb{Q}^k using a strongly polynomial algorithm in the Turing model.

Note that stepwise strong polynomiality does not require that the total number of iterations TT is strongly polynomially bounded. Most standard interior point methods, such as the predictor-corrector method [35], are stepwise strongly polynomial: computing each step direction amounts to solving a system of linear equations, where the coefficients are constructed from the input (A,b,c)(A,b,c) and the current iterate. Accordingly, the bit complexity of the iterates might grow by a polynomial factor in each iteration. Thus, after a superconstant number of iterations, we would not be able to guarantee that the bit complexity of the iterates remains polynomially bounded in the input length.

Consequently, even if an iterative algorithm terminates in a strongly polynomial number of iterations, and is stepwise strongly polynomial, it does not follow that the algorithm is strongly polynomial in the Turing model.

The difficulty of rounding in the strongly polynomial model. To implement an IPM in PSPACE, a natural idea is to use additional rounding steps. In the weakly polynomial model, i.e., when running time dependence on the total encoding length is allowed, the bit complexity of the algorithms can be controlled by approximate linear system solves and rounding. Recent work by Ghadiri, Peng, and Vempala [22] developed general tools that enable one to keep the bit complexity of recent fast IPMs under control.

However, these techniques are not applicable in the strongly polynomial Turing model, where the number of arithmetic operations and comparisons must be bounded independently of the encoding length. In this model one cannot even approximate log⁡(x)\log(x) to within an additive constant for large xx.

As already mentioned, Theorem 1.8 in this paper presents a general, strongly polynomial rounding technique that can be used to convert—under certain technical conditions—any stepwise strongly polynomial interior point method that stays in the ℓ2\ell_2-neighborhood to a PSPACE algorithm.

The central path and the analytic center

We next formally introduce some concepts from the theory of interior point methods needed to define straight-line complexity and to state our results. Given an instance of LP⁡(A,b,c)\operatorname{LP}(A,b,c), we let

P:={x∈Rn∣Ax=b, x≥0},P>0:=P∩R>0n,\mathcal{P} := \{x \in\mathbb{R}^{n} \mid Ax=b,\ x\geq0\}, \qquad\mathcal{P}_{>0}:=\mathcal{P}\cap\mathbb{R}_{>0}^{n},
D:={s∈Rn∣∃y∈Rm, ATy+s=c, s≥0},D>0:=D∩R>0n.\mathcal{D} := \{s\in\mathbb{R}^{n}\mid\exists y\in\mathbb{R}^{m},\ A^{\mathsf{T}}y+s=c,\ s\geq0\}, \qquad\mathcal{D}_{>0}:=\mathcal{D}\cap\mathbb{R}_{>0}^{n}.

denote the primal and dual feasible regions, and the sets of strictly feasible primal and dual solutions, respectively. For (x,s)∈P×D(x,s)\in\mathcal{P}\times\mathcal{D}, the normalized duality gap is

μˉ(x,s):=⟨x,s⟩n.\bar{\mu}(x,s):=\frac{\langle x,s\rangle}{n}.

By complementary slackness, (x,s)∈P×D(x,s)\in\mathcal{P}\times\mathcal{D} is a pair of primal and dual optimal solutions if and only if μˉ(x,s)=0\bar{\mu}(x,s)=0.

References

  1. [1]X. Allamigeon, P. Benchimol, S. Gaubert, and M. Joswig. Log-barrier interior point methods are not strongly polynomial. SIAM Journal on Applied Algebra and Geometry, 2(1):140–178, 2018. 1, 2DOI
  2. [2]X. Allamigeon, D. Dadush, G. Loho, B. Natura, and L. A. Végh. Interior point methods are not worse than Simplex. SIAM Journal on Computing, 54(5):FOCS22-178–FOCS22-264, 2025. 1, 2, 3, 4, 5, 6, 7, 25, 26, 28, 32
  3. [3]X. Allamigeon, S. Gaubert, and N. Vandame. No self-concordant barrier interior point method is strongly polynomial. In Proceedings of the 54th Annual ACM Symposium on Theory of Computing (STOC), pages 515–528, 2022. 1, 2arxiv.org/abs/2201.02186
  4. [4]J. van den Brand, L. Chen, R. Kyng, Y. P. Liu, R. Peng, M. Probst Gutenberg, S. Sachdeva, and A. Sidford. A deterministic almost-linear time algorithm for minimum-cost flow. In Proceedings of the 64th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 503–514, 2023. 1arxiv.org/abs/2309.16629
  5. [5]J. van den Brand, Y. T. Lee, A. Sidford, and Z. Song. Solving tall dense linear programs in nearly linear time. In Proceedings of the 52nd Annual ACM Symposium on Theory of Computing (STOC), pages 775–788, 2020. 1arxiv.org/abs/2002.02304
  6. [6]P. A. Beling and N. Megiddo. Using fast matrix multiplication to find basic solutions. Theoretical Computer Science, 205(1–2):307–316, 1998. 41DOI
  7. [7]J. van den Brand. A deterministic linear program solver in current matrix multiplication time. In Proceedings of the 2020 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 259–278. SIAM, 2020. 1arxiv.org/abs/1910.11957
  8. [8]L. Blum, M. Shub, and S. Smale. On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines. Bulletin of the American Mathematical Society, 21(1):1–46, 1989. 3
  9. [9]J. van den Brand and D. J. Zhang. Faster high accuracy multi-commodity flow from single-commodity techniques. In Proceedings of the 64th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 493–502, 2023. 1arxiv.org/abs/2304.12992
  10. [10]S. Chubanov. A polynomial algorithm for linear optimization which is strongly polynomial under certain conditions on optimal solutions, 2015. Working paper, Bosch Center for Artificial Intelligence, Siegen, Germany. 2
  11. [11]L. Chen, R. Kyng, Y. P. Liu, R. Peng, M. Probst Gutenberg, and S. Sachdeva. Maximum flow and minimum-cost flow in almost-linear time. Journal of the ACM, 72(3):1–103, 2025. 1
  12. [12]M. B. Cohen, Y. T. Lee, and Z. Song. Solving linear programs in the current matrix multiplication time. Journal of the ACM, 68(1):1–39, 2021. 1
  13. [13]H. Cohen. A Course in Computational Algebraic Number Theory, volume 138 of Graduate Texts in Mathematics. Springer, 1993. 39DOI
  14. [15]D. Dadush, Z. K. Koh, B. Natura, N. Olver, and L. A. Végh. A strongly polynomial algorithm for linear programs with at most two nonzero entries per row or column. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC), pages 1561–1572, 2024. 1, 2DOI
  15. [16]D. Dadush, Z. K. Koh, B. Natura, N. Olver, and L. A. Végh. A strongly polynomial algorithm for the minimum-cost generalized flow problem. Companion paper, in preparation, 2026. 1, 2
  16. [17]D. Dadush, H. Ma, B. Natura, and L. A. Végh. Trust region interior point methods: Optimal ℓ₂- and faster wide-neighborhood path following. In Proceedings of the 58th Annual ACM Symposium on Theory of Computing (STOC), pages 755–766, 2026.DOI
  17. [18]D. Dadush, B. Natura, and L. A. Végh. Revisiting Tardos’s framework for linear programming: Faster exact solutions using approximate solvers. In Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 931–942, 2020.arxiv.org/abs/2009.04942
  18. [19]J. Edmonds. Systems of distinct representatives and linear algebra. J. Res. Nat. Bur. Standards Sect. B, 71(4):241–245, 1967.
  19. [20]M. Grötschel, L. Lovász, and A. Schrijver. Geometric algorithms and combinatorial optimization, volume 2 of Algorithms and Combinatorics. Springer, 1988.
  20. [21]C. C. Gonzaga. Path-following methods for linear programming. SIAM Review, 34(2):167–224, 1992.DOI
  21. [22]M. Ghadiri, R. Peng, and S. S. Vempala. The bit complexity of efficient continuous optimization. In Proceedings of the 64th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 2059–2070, 2023.arxiv.org/abs/2304.02124
  22. [23]A. J. Goldman and A. W. Tucker. Theory of linear programming. Linear inequalities and related systems, 38:53–97, 1956.
  23. [24]D. S. Hochbaum. Monotonizing linear programs with up to two nonzeroes per column. Operations Research Letters, 32(1):49–58, 2004.DOI
  24. [25]S.-H. Hou. Classroom note: A simple proof of the Leverrier–Faddeev characteristic polynomial algorithm. SIAM Review, 40(3):706–709, 1998.DOI
  25. [26]S. Jiang, Z. Song, O. Weinstein, and H. Zhang. A faster algorithm for solving general LPs. In Proceedings of the 53rd Annual ACM Symposium on Theory of Computing (STOC), pages 823–832, 2021.DOI
  26. [27]N. Karmarkar. A new polynomial-time algorithm for linear programming. In Proceedings of the 16th Annual ACM Symposium on Theory of Computing (STOC), pages 302–311, 1984.
  27. [28]L. G. Khachiyan. A polynomial algorithm in linear programming. Doklady Akademii Nauk SSSR, 244(5):1093–1096, 1979.
  28. [29]G. Lan, R. D. C. Monteiro, and T. Tsuchiya. A polynomial predictor-corrector trust-region algorithm for linear programming. SIAM Journal on Optimization, 19(4):1918–1946, 2009.DOI
  29. [30]U. J. J. Le Verrier. Sur les variations séculaires des éléments elliptiques des sept planètes principales: Mercure, Vénus, la Terre, Mars, Jupiter, Saturne et Uranus. Journal de Mathématiques Pures et Appliquées, 5:220–254, 1840.
  30. [31]N. Megiddo. Towards a genuinely polynomial algorithm for linear programming. SIAM Journal on Computing, 12(2):347–353, 1983.
  31. [32]N. Megiddo, S. Mizuno, and T. Tsuchiya. A modified layered-step interior-point algorithm for linear programming. Mathematical Programming, 82(3):339–355, 1998.DOI
  32. [33]R. D. C. Monteiro and T. Tsuchiya. A variant of the Vavasis-Ye layered-step interior-point algorithm for linear programming. SIAM Journal on Optimization, 13(4):1054–1079, 2003.DOI
  33. [34]R. D. C. Monteiro and T. Tsuchiya. A new iteration-complexity bound for the MTY predictor-corrector algorithm. SIAM Journal on Optimization, 15(2):319–347, 2005.DOI
  34. [35]S. Mizuno, M. J. Todd, and Y. Ye. On adaptive-step primal-dual interior-point algorithms for linear programming. Mathematics of Operations Research, 18(4):964–981, 1993.
  35. [36]N. Olver and L. A. Végh. A simpler and faster strongly polynomial algorithm for generalized flow maximization. Journal of the ACM, 67(2):1–26, 2020.

Paper details

vlnc:W_hq93zgsf
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

GPT-6 Astra, Claude Opus 5.5

View statement
Looking for related papers…
Contents