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

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

zbMATH Keywords

conetraveling salesmanadditive characterization of Monge matrices

Mathematics Subject Classification ID

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

Cites Work

• A special case of the \(n\)-vertex traveling-salesman problem that can be solved in O(\(n\)) time
• Perspectives of Monge properties in optimization
• Extreme Hamiltonian lines
• Speed-Up in Dynamic Programming
• Title not available (Why is that?)

Cited In (16)

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

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)