Solving linear programs from sign patterns

DOI10.1007/s10107-007-0107-7zbMath1145.90040OpenAlexW2086465778MaRDI QIDQ927161

Satoru Iwata, Naonori Kakimura

Publication date: 4 June 2008

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-007-0107-7

Mathematics Subject Classification ID

Linear programming (90C05) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Related Items

Matching structure of symmetric bipartite graphs and a generalization of Pólya's problem ⋮ Trichotomy for integer linear systems based on their sign patterns ⋮ Complex-\(L\) matrix and its recognition ⋮ Sign-solvable linear complementarity problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On matrices which have signed null-spaces
• A new polynomial-time algorithm for linear programming
• Signsolvability revisited
• Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs
• Characterization of even directed graphs
• Matching theory
• Robust solutions of uncertain linear programs
• Sign-central matrices
• Advances in sensitivity analysis and parametric programming
• Some properties of matrices with signed null spaces.
• Linear systems with signed solutions
• Pólya's permanent problem
• Permanents, Pfaffian orientations, and even directed circuits
• Brace generation
• Linear programming with interval coefficients
• Sign-consistency and solvability of constrained linear systems
• Faster Scaling Algorithms for Network Problems
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs