Monge matrices make maximization manageable

DOI10.1016/0167-6377(94)90037-XMaRDI QIDQ1890948zbMATH OpenOpenAlexFDO

Authors Ulrich Pferschy, Rüdiger Rudolf, Gerhard J. Woeginger

Publication date 28 May 1995

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0167-6377(94)90037-x

zbMATH Keywords

Monge matrixMonge propertybalanced cut\(k\)- matchingdistribution matrixlongest paths in bipartite, edge-weighted graphsMonge structures

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Recommendations

• A matrix generalization of a vector maximization problem
• Computing an eigenvector of a Monge matrix in max-plus algebra
• On the matrix Monge–Kantorovich problem
• On maximum principles for monotone matrices
• Publication:3028741
• Computing an eigenvector of an inverse Monge matrix in max-plus algebra
• The maximum matrix contraction problem
• Optimal solutions of the Monge problem
• Special properties of Monge matrices in max-plus algebra
• A Matrix Maximum

Cites work

• scientific article; zbMATH DE number 4027206 (Why is no real title available?)
• scientific article; zbMATH DE number 49142 (Why is no real title available?)
• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3895002 (Why is no real title available?)
• scientific article; zbMATH DE number 3272833 (Why is no real title available?)
• A special case of the \(n\)-vertex traveling-salesman problem that can be solved in O(\(n\)) time
• Extreme Hamiltonian lines
• Fibonacci heaps and their uses in improved network optimization algorithms
• Finding a minimum-weight k-link path in graphs with the concave Monge property and applications
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• Some simplified NP-complete graph problems
• Special cases of travelling salesman problems and heuristics
• The NP-completeness column: an ongoing guide

Cited in

(8)

• Spanning trees and shortest paths in Monge graphs
• Equally weighted cardinality constrained portfolio selection via factor models
• Well-solvable cases of the QAP with block-structured matrices
• Fast distance multiplication of unit-Monge matrices
• Fast distance multiplication of unit-Monge matrices
• Perspectives of Monge properties in optimization
• On the role of bottleneck Monge matrices in combinatorial optimization
• Estimation of Monge matrices

This page was built for publication: Monge matrices make maximization manageable

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