Improved Algorithms For Linear Inequalities with Two Variables Per Inequality

DOI10.1137/S0097539791256325MaRDI QIDQ4327426zbMATH OpenOpenAlexFDO

Authors Edith Cohen, Nimrod Megiddo

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

zbMATH Keywords

linear inequalitieslinear systemsparallel implementationstrongly polynomial algorithmstwo-variable inequalities

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Parallel numerical computation (65Y05) Linear programming (90C05) Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• Simple and Fast Algorithms for Linear and Integer Programs with Two Variables Per Inequality
• Improved NP-inapproximability for 2-variable linear equations
• scientific article; zbMATH DE number 6823767
• Linear Programming with Two Variables Per Inequality in Poly-Log Time
• scientific article; zbMATH DE number 934404
• A new algorithm for solving linear inequalities systems problems
• New iterative methods for linear inequalities
• Exact algorithms for linear matrix inequalities
• Improved deterministic algorithms for linear programming in low dimensions
• Improved deterministic algorithms for linear programming in low dimensions

Cited in

(16)

• New algorithms for generalized network flows
• Monotonizing linear programs with up to two nonzeroes per column
• Incremental closure for systems of two variables per inequality
• A linear programming primer: from Fourier to Karmarkar
• Parameterized complexity of sparse linear complementarity problems
• scientific article; zbMATH DE number 3883605 (Why is no real title available?)
• The Linear Complementarity Problems with a Few Variables per Constraint
• On memoryless provers and insincere verifiers
• scientific article; zbMATH DE number 6823767 (Why is no real title available?)
• A simple GAP-canceling algorithm for the generalized maximum flow problem
• A faster algorithm for determining the linear feasibility of systems of BTVPI constraints
• Minimizing convex functions with rational minimizers
• A set partitioning reformulation of a school bus scheduling problem
• A generalized approximation framework for fractional network flow and packing problems
• Bimonotone linear inequalities and sublattices of \(\mathbb R^n\)
• Efficient non-myopic value-of-information computation for influence diagrams

This page was built for publication: Improved Algorithms For Linear Inequalities with Two Variables Per Inequality

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4327426)