The cone of Monge matrices: Extremal rays and applications

DOI10.1007/BF01415751zbMATH Open0843.90101OpenAlexW2063528310MaRDI QIDQ4861874FDOQ4861874

Authors Rüdiger Rudolf, Gerhard J. Woeginger 

Publication date 23 January 1996

Published in ZOR Zeitschrift f�r Operations Research Methods and Models of Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01415751

zbMATH Keywords

conetraveling salesmanadditive characterization of Monge matrices

Mathematics Subject Classification ID

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

Recommendations

• Conic characterization of Monge matrices
• scientific article; zbMATH DE number 2073529
• Perspectives of Monge properties in optimization
• On the recognition of permuted Supnick and incomplete Monge matrices
• On the traveling salesman problem with a relaxed Monge matrix

Cites work

• scientific article; zbMATH DE number 4189491 (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
• Perspectives of Monge properties in optimization
• Speed-Up in Dynamic Programming

Cited in

(16)

• Conic characterization of Monge matrices
• Extremal rays of the equivariant Littlewood-Richardson cone
• Equilibrated anti-Monge matrices
• The cone of flow matrices: Approximation hierarchies and applications
• Estimation of Monge matrices
• A comment on consecutive-2-out-of-\(n\) systems
• The extreme rays of the \(5 \times 5\) copositive cone
• The complexity of approximating conservative counting CSPs
• Another well-solvable case of the QAP: maximizing the job completion time variance
• Well-solvable cases of the QAP with block-structured matrices
• Perspectives of Monge properties in optimization
• Robinsonian matrices: recognition challenges
• On totally positive matrices and geometric incidences
• A complexity classification of spin systems with an external field
• New special cases of the quadratic assignment problem with diagonally structured coefficient matrices
• scientific article; zbMATH DE number 2073529 (Why is no real title available?)

This page was built for publication: The cone of Monge matrices: Extremal rays and applications

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