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 problemcharacteristic max-polynomialessential termsmax-algebraparametric optimization

Mathematics Subject Classification ID

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

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

• 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.
• scientific article; zbMATH DE number 3702681 (Why is no real title available?)
• 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

(20)

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

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)