Systems of distinct representatives and linear algebra
From MaRDI portal
Publication:5564386
DOI10.6028/jres.071B.033zbMath0178.03002OpenAlexW2050735826MaRDI QIDQ5564386
Publication date: 1967
Published in: Journal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.6028/jres.071b.033
Related Items
A strongly polynomial minimum cost circulation algorithm, Non-interval greedoids and the transposition property, On the computation of pfaffians, Solving systems of linear equations over polynomials, Irreducibility of multivariate polynomials, Algorithmic properties of maximal orders in simple algebras over \(\mathbb{Q}\), Classical complexity and quantum entanglement, An adaptable and extensible geometry kernel, Constructive non-commutative rank computation is in deterministic polynomial time, König's theorem and bimatroids, Some combinatorial-algebraic problems from complexity theory, Factorization properties of lattices over the integers, Exact arborescences, matchings and cycles, Matching is as easy as matrix inversion, A primal-dual interior point method whose running time depends only on the constraint matrix, Note on separation from membership, and folklore, An application of simultaneous diophantine approximation in combinatorial optimization, On computational complexity of construction of c -optimal linear regression models over finite experimental domains, A greedy algorithm for hereditary set systems and a generalization of the Rado-Edmonds characterization of matroids, On Chubanov’s Method for Solving a Homogeneous Inequality System, Quadratic programming is in NP, Closedness of Integer Hulls of Simple Conic Sets, Constructing a perfect matching is in random NC, On the Implementation of Combinatorial Algorithms for the Linear Exchange Market, A fully polynomial time projective method, A matroid on hypergraphs, with applications in scene analysis and geometry, A cost-scaling algorithm for computing the degree of determinants, Exact and Heuristic Algorithms for Semi-Nonnegative Matrix Factorization, Algebraic and numerical techniques for the computation of matrix determinants, Narrow sieves for parameterized paths and packings, Simultaneous robust subspace recovery and semi-stability of quiver representations, Bracing cubic grids - a necessary condition, On the complexity of finding tensor ranks, Non-commutative Edmonds' problem and matrix semi-invariants, Tripartite-to-bipartite entanglement transformation by stochastic local operations and classical communication and the structure of matrix spaces, Extension of partial diagonals of matrices. II, Some results involving the splitting operation on binary matroids, Factoring multivariate polynomials represented by black boxes: a Maple + C implementation, Network theory and transversal matroids, General approximation schemes for min-max (regret) versions of some (pseudo-)polynomial problems, Towards a strongly polynomial algorithm for strictly convex quadratic programs: An extension of Tardos' algorithm, A polynomial-time recursive algorithm for some unconstrained quadratic optimization problems, Computing the sign or the value of the determinant of an integer matrix, a complexity survey., Complexity of linear programming, An algorithm for linear programming which requires \(O(((m+n)n^ 2+(m+n)^{1.5}n)L)\) arithmetic operations, Subtree isomorphism is in random NC, Cardinality constrained minimum cut problems: complexity and algorithms., Subspace Arrangements, Graph Rigidity and Derandomization Through Submodular Optimization, On a weighted linear matroid intersection algorithm by deg-det computation, The image of weighted combinatorial problems, Identifying lens spaces in polynomial time, On the complexity of generalized chromatic polynomials, Random pseudo-polynomial algorithms for some combinatorial programming problems, Finding a low-rank basis in a matrix subspace, The double pivot simplex method, Polynomial algorithms for LP over a subring of the algebraic integers with applications to LP with circulant matrices, Lee-Yang theorems and the complexity of computing averages, On the spanning trees of weighted graphs, Feasible partition problem in reverse convex and convex mixed-integer programming, Expansive automata networks, On the free matrix representation of transversal geometries, Partial matroid representations, A strongly polynomial algorithm for linear systems having a binary solution, On the rank and periodic rank of finite dynamical systems, Linear matroid intersection is in quasi-NC, Combinatorial aspects of rectangular non-negative matrices, Roundoff-Error-Free Algorithms for Solving Linear Systems via Cholesky and LU Factorizations, Many-visits TSP revisited, A polynomial projection algorithm for linear feasibility problems, A computational basis for higher-dimensional computational geometry and applications, Singular tuples of matrices is not a null cone (and the symmetries of algebraic varieties), Spanning tree constrained determinantal point processes are hard to (approximately) evaluate, Matroids on partially ordered sets, Operator scaling: theory and applications, The optimal path-matching problem, A combinatorial algorithm for computing the degree of the determinant of a generic partitioned polynomial matrix with \(2\times 2\) submatrices, Some recent results in combinatorial approaches to dynamical systems, Extension of partial diagonals of matrices. I, Matrix scaling and explicit doubly stochastic limits, Computing in combinatorial optimization, Edmonds' problem and the membership problem for orbit semigroups of quiver representations, Solving minimum K-cardinality cut problems in planar graphs, The complexity of solution-free sets of integers for general linear equations, A combinatorial algorithm for computing the rank of a generic partitioned matrix with \(2 \times 2\) submatrices, A network theory approach to the rigidity of skeletal structures. I: Modelling and interconnection, Brick decompositions and the matching rank of graphs, Maps of matroids with applications, Frontiers of sphere recognition in practice, The computational complexity of some problems of linear algebra, Definability and fast quantifier elimination in algebraically closed fields, Computing valuations of the Dieudonné determinants, A note on locality of algebras, Which pivot to solve linear systems?, Factoring multivariate polynomials over finite fields, Polynomial-time algorithms for quadratic isomorphism of polynomials: the regular case, Generalized Wong sequences and their applications to Edmonds' problems, Solvability by radicals is in polynomial time, A fast parallel algorithm for minimum-cost small integral flows, Some sequences associated with combinatorial structures, Totally tight Chvatal-Gomory cuts, Algorithm 1021: SPEX Left LU, Exactly Solving Sparse Linear Systems via a Sparse Left-looking Integer-preserving LU Factorization, A Combinatorial Algorithm for Computing the Rank of a Generic Partitioned Matrix with 2 $$\times $$ 2 Submatrices, Constructive Non-Commutative Rank Computation Is in Deterministic Polynomial Time., SOS Is Not Obviously Automatizable, Even Approximately, Identifiability of a simultaneous equations model of economy: a structural view, Exactly Solving Sparse Rational Linear Systems via Roundoff-Error-Free Cholesky Factorizations, Singular spaces of matrices and their application in combinatorics, A graph-theoretic approach to investigate structural and qualitative properties of systems: A survey, Minimization of even conic functions on the two-dimensional integral lattice, Combinatorial Canonical Form of Layered Mixed Matrices and Its Application to Block-Triangularization of Systems of Linear/Nonlinear Equations, Connections between graphs and matrix spaces, A combinatorial algorithm for computing the entire sequence of the maximum degree of minors of a generic partitioned polynomial matrix with \(2 \times 2\) submatrices, Presentations of transversal valuated matroids, Roundoff-Error-Free Basis Updates of LU Factorizations for the Efficient Validation of Optimality Certificates, An approximation algorithm for indefinite mixed integer quadratic programming, Interactions of computational complexity theory and mathematics, Exact QR factorizations of rectangular matrices, Matroids and the greedy algorithm, An improved version of Chubanov's method for solving a homogeneous feasibility problem, On the spanning trees of weighted graphs, Detecting and Counting Small Pattern Graphs, On the Foundations of Combinatorial Theory: IX Combinatorial Methods in Invariant Theory, Maximum Rank of Powers of a Matrix of a Given Pattern, The inverse of a non-singular free matrix, Unnamed Item, Computing the nc-Rank via Discrete Convex Optimization on CAT(0) Spaces, Linear programming using limited-precision oracles, Exact Solution of Sparse Linear Systems via Left-Looking Roundoff-Error-Free LU Factorization in Time Proportional to Arithmetic Work, Computing the Degree of Determinants via Discrete Convex Optimization on Euclidean Buildings, Shortest Two Disjoint Paths in Polynomial Time, Polynomial algorithms for a class of linear programs, Unnamed Item, Matrices of Optimal Tree-Depth and a Row-Invariant Parameterized Algorithm for Integer Programming
