Improved Algorithms For Linear Inequalities with Two Variables Per Inequality
From MaRDI portal
Publication:4327426
DOI10.1137/S0097539791256325zbMath0833.90094OpenAlexW2019609597MaRDI QIDQ4327426
Publication date: 6 April 1995
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539791256325
linear systemsparallel implementationlinear inequalitiesstrongly polynomial algorithmstwo-variable inequalities
Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05) Combinatorial optimization (90C27) Parallel numerical computation (65Y05) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
New algorithms for generalized network flows ⋮ The Linear Complementarity Problems with a Few Variables per Constraint ⋮ Parameterized complexity of sparse linear complementarity problems ⋮ A linear programming primer: from Fourier to Karmarkar ⋮ A faster algorithm for determining the linear feasibility of systems of BTVPI constraints ⋮ A set partitioning reformulation of a school bus scheduling problem ⋮ Monotonizing linear programs with up to two nonzeroes per column ⋮ Incremental closure for systems of two variables per inequality ⋮ A generalized approximation framework for fractional network flow and packing problems ⋮ A simple GAP-canceling algorithm for the generalized maximum flow problem ⋮ Efficient non-myopic value-of-information computation for influence diagrams ⋮ On memoryless provers and insincere verifiers ⋮ Bimonotone linear inequalities and sublattices of \(\mathbb R^n\)
