Towards a Genuinely Polynomial Algorithm for Linear Programming
From MaRDI portal
Publication:3315270
DOI10.1137/0212022zbMath0532.90061OpenAlexW2002636386MaRDI QIDQ3315270
Publication date: 1983
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0212022
computational complexitylinear inequalitiesconvex minimizationbinary searchat most two variables per inequalitygenuinely polynomial algorithm
Related Items (27)
A strongly polynomial minimum cost circulation algorithm ⋮ New algorithms for generalized network flows ⋮ On the complexity of quadratic programming in real number models of computation ⋮ Polynomial algorithms for linear programming over the algebraic numbers ⋮ The complexity of resource allocation and price mechanisms under bounded rationality ⋮ Optimal Embedding into Star Metrics ⋮ Bounds on the complexity of halfspace intersections when the bounded faces have small dimension ⋮ A strongly polynomial algorithm for a new class of linear inequalities1 ⋮ A linear programming primer: from Fourier to Karmarkar ⋮ On genuinely time bounded computations ⋮ A Strongly Polynomial Algorithm for Generalized Flow Maximization ⋮ Is binary encoding appropriate for the problem-language relationship? ⋮ Constraint Satisfaction Problems over Numeric Domains ⋮ A set partitioning reformulation of a school bus scheduling problem ⋮ Detecting matrices of combinatorial rank three ⋮ Integer programs for logic constraint satisfaction ⋮ Polynomial algorithms for LP over a subring of the algebraic integers with applications to LP with circulant matrices ⋮ Low-rank matrix approximation in the infinity norm ⋮ Minimizing mean weighted execution time loss on identical and uniform processors ⋮ Range assignment of base-stations maximizing coverage area without interference ⋮ Testing the necklace condition for shortest tours and optimal factors in the plane ⋮ Some aspects of studying an optimization or decision problem in different computational models ⋮ Locating service centers with precedence constraints ⋮ Algorithms and complexity analysis for some flow problems ⋮ An algorithm of internal feasible directions for linear integer programming ⋮ A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix ⋮ Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality
This page was built for publication: Towards a Genuinely Polynomial Algorithm for Linear Programming
