The cone of Monge matrices: Extremal rays and applications

DOI10.1007/BF01415751MaRDI QIDQ4861874zbMATH OpenOpenAlexFDO

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

additive characterization of Monge matricesconetraveling salesman

Mathematics Subject Classification ID

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

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

• A special case of the \(n\)-vertex traveling-salesman problem that can be solved in O(\(n\)) time
• Extreme Hamiltonian lines
• scientific article; zbMATH DE number 4189491 (Why is no real title available?)
• Perspectives of Monge properties in optimization
• Speed-Up in Dynamic Programming

Cited in

(16)

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

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)