The cone of Monge matrices: Extremal rays and applications

DOI10.1007/BF01415751zbMath0843.90101OpenAlexW2063528310MaRDI QIDQ4861874

Rüdiger Rudolf, Gerhard J. Woeginger

Publication date: 23 January 1996

Published in: [https://portal.mardi4nfdi.de/entity/Q3031760 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)

Related Items

Robinsonian matrices: recognition challenges ⋮ Perspectives of Monge properties in optimization ⋮ A complexity classification of spin systems with an external field ⋮ Estimation of Monge matrices ⋮ On totally positive matrices and geometric incidences ⋮ 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 ⋮ A comment on consecutive-2-out-of-\(n\) systems ⋮ Equilibrated anti-Monge matrices ⋮ The complexity of approximating conservative counting CSPs ⋮ Well-solvable cases of the QAP with block-structured matrices

Cites Work

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