Using fast matrix multiplication to find basic solutions

DOI10.1016/S0304-3975(98)00003-6zbMath0913.68079OpenAlexW2068835684MaRDI QIDQ1275090

Nimrod Megiddo, Peter A. Beling

Publication date: 12 January 1999

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(98)00003-6

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

(De)randomized construction of small sample spaces in \(\mathcal{NC}\), Bin covering with cardinality constraints, Approximation schemes for packing with item fragmentation, Fast rectangular matrix multiplication and some applications, An improved approximation scheme for variable-sized bin packing, Fully dynamic bin packing revisited, Approximation Schemes for Machine Scheduling with Resource (In-)dependent Processing Times, Finding mixed strategies with small supports in extensive form games, Robust algorithms for preemptive scheduling on uniform machines of non-increasing job sizes, Fast rectangular matrix multiplication and applications, A Robust AFPTAS for Online Bin Packing with Polynomial Migration

Cites Work

• How to multiply matrices faster
• Matrix multiplication via arithmetic progressions
• On the computational power of pushdown automata
• Rapid Multiplication of Rectangular Matrices
• On Finding Primal- and Dual-Optimal Bases
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item