Using fast matrix multiplication to find basic solutions

DOI10.1016/S0304-3975(98)00003-6MaRDI QIDQ1275090zbMATH OpenOpenAlexFDO

Authors Peter A. Beling, Nimrod Megiddo

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)

Recommendations

• Fast rectangular matrix multiplication and applications
• Fast rectangular matrix multiplication and some applications
• Linear Programming in O([n3/ln n]L) Operations
• Solving Linear Programs in the Current Matrix Multiplication Time

Cites work

• How to multiply matrices faster
• scientific article; zbMATH DE number 4213315 (Why is no real title available?)
• scientific article; zbMATH DE number 3688713 (Why is no real title available?)
• scientific article; zbMATH DE number 3628660 (Why is no real title available?)
• scientific article; zbMATH DE number 1142301 (Why is no real title available?)
• Matrix multiplication via arithmetic progressions
• On Finding Primal- and Dual-Optimal Bases
• On the computational power of pushdown automata
• Rapid Multiplication of Rectangular Matrices

Cited in

(14)

• Fast rectangular matrix multiplication and applications
• (De)randomized construction of small sample spaces in \(\mathcal{NC}\)
• Finding mixed strategies with small supports in extensive form games
• Robust algorithms for preemptive scheduling on uniform machines of non-increasing job sizes
• Fully dynamic bin packing revisited
• Bin covering with cardinality constraints
• On exact algorithm of the method of basic matrices
• Approximation schemes for machine scheduling with resource (in-)dependent processing times
• An improved approximation scheme for variable-sized bin packing
• A robust AFPTAS for online bin packing with polynomial migration
• Scheduling with cardinality dependent unavailability periods
• The bit complexity of dynamic algebraic formulas and their determinants
• Approximation schemes for packing with item fragmentation
• Fast rectangular matrix multiplication and some applications

This page was built for publication: Using fast matrix multiplication to find basic solutions

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