Primal-Dual Combinatorial Relaxation Algorithms for the Maximum Degree of Subdeterminants

DOI10.1137/0917064MaRDI QIDQ4891748zbMATH OpenOpenAlexFDO

Authors Satoru Iwata, Kazuo Murota, Izumi Sakuta

Publication date 1 October 1997

Published in SIAM Journal on Scientific Computing (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/2433/59713

zbMATH Keywords

algorithmscombinatorial optimizationassignment problemdifferential algebraic equationsminorrational function matrixKronecker formmaximal degreesubdeterminantSmith-McMillan form at infinity

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Determinants, permanents, traces, other special matrix functions (15A15) Matrix pencils (15A22) Discrete location and assignment (90B80) Matrices over function rings in one or more variables (15A54) Numerical computation of determinants (65F40)

Recommendations

• A combinatorial, primal-dual approach to semidefinite programs
• Computing the maximum degree of minors in matrix pencils via combinatorial relaxation
• scientific article; zbMATH DE number 1305439
• Primal-dual enumeration for multiparametric linear programming
• A class of convergent primal-dual subgradient algorithms for decomposable convex programs
• The primal-dual method for approximation algorithms
• Computational results with a primal-dual subproblem simplex method
• Complexity analysis of primaldual algorithms for the semidefinite linear complementarity problem
• Primal-dual subgradient methods for convex problems
• An algebraic theory for primal and dual substructuring methods by constraints

Cited in

(11)

• Combinatorial relaxation algorithm for mixed polynomial matrices
• Computing the maximum degree of minors in mixed polynomial matrices via combinatorial relaxation
• Computing the maximum degree of minors in mixed polynomial matrices via combinatorial relaxation
• Index reduction via unimodular transformations
• Index reduction for differential-algebraic equations by substitution method
• An algebraic theory for primal and dual substructuring methods by constraints
• Computing the maximum degree of minors in matrix pencils via combinatorial relaxation
• Two algorithms for valuated \(\Delta\)-matroids
• Combinatorial relaxation algorithm for the maximum degree of subdeterminants: Computing Smith-McMillan form at infinity and structural indices in Kronecker form
• Combinatorial relaxation algorithm for the entire sequence of the maximum degree of minors
• 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

This page was built for publication: Primal-Dual Combinatorial Relaxation Algorithms for the Maximum Degree of Subdeterminants

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