A fast parametric assignment algorithm with applications in max-algebra

DOI10.1002/NET.20288MaRDI QIDQ3057132zbMATH OpenOpenAlexFDO

Authors Elisabeth Gassner, Bettina Klinz

Publication date 24 November 2010

Published in Networks (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/net.20288

zbMATH Keywords

assignment problemparametric optimizationmax-algebracharacteristic max-polynomialessential terms

Mathematics Subject Classification ID

Sensitivity, stability, parametric optimization (90C31) Discrete location and assignment (90B80)

Recommendations

• Calculating essential terms of a characteristic maxpolynomial
• Finding all essential terms of a characteristic maxpolynomial.
• An algorithm for fractional assignment problems
• scientific article; zbMATH DE number 176471
• Max algebra and the linear assignment problem

Cites work

• scientific article; zbMATH DE number 3702681 (Why is no real title available?)
• A Fast Parametric Maximum Flow Algorithm and Applications
• Complexity of some parametric integer and network programming problems
• Computational complexity of parametric linear programming
• Faster parametric shortest path and minimum‐balance algorithms
• Finding all essential terms of a characteristic maxpolynomial.
• Mathematical Techniques for Efficient Record Segmentation in Large Shared Databases
• Network flows. Theory, algorithms, and applications.
• On a routing problem
• Parametric shortest path algorithms with an application to cyclic staffing
• The characteristic maxpolynomial of a matrix
• The complexity of computing the permanent

Cited in

(18)

• Calculating essential terms of a characteristic maxpolynomial
• scientific article; zbMATH DE number 1256749 (Why is no real title available?)
• Algorithm for the CSR expansion of max-plus matrices using the characteristic polynomial
• Non-archimedean valuations of eigenvalues of matrix polynomials
• Triangulation of diagonally dominant min-plus matrices
• The non-positive circuit weight problem in parametric graphs: a solution based on dioid theory
• Finding all essential terms of a characteristic maxpolynomial.
• Computing the sequence of \(k\)-cardinality assignments
• On the numerical range in tropical algebra
• Tropical bounds for eigenvalues of matrices
• An approximation algorithm for a general class of parametric optimization problems
• Characterization and algorithm for max-plus supereigenvector problem by parametric programming
• On tropical eigenvalues of tridiagonal Toeplitz matrices
• Max-plus singular values
• An approximation algorithm for a general class of multi-parametric optimization problems
• A survey of exact and approximation algorithms for linear-parametric optimization problems
• Max-max, max-min, min-max and min-min knapsack problems with a parametric constraint
• Parametric matroid interdiction

This page was built for publication: A fast parametric assignment algorithm with applications in max-algebra

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