Monge matrices make maximization manageable

DOI10.1016/0167-6377(94)90037-XzbMATH Open0822.90112OpenAlexW2120283278MaRDI QIDQ1890948FDOQ1890948

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

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

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)

Cites Work

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

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)