A linear time algorithm for linearizing quadratic and higher-order shortest path problems

DOI10.1007/978-3-031-32726-1_33zbMath1528.90209arXiv2303.00569MaRDI QIDQ6086024

Lasse Wulf, Stefan Lendl, Bettina Klinz, Gerhard J. Woeginger, Eranda Çela

Publication date: 9 November 2023

Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2303.00569

zbMATH Keywords

linearizationquadratic shortest path problemhigher-order shortest path problem

Mathematics Subject Classification ID

Quadratic programming (90C20) Combinatorial optimization (90C27)

Cites Work

• Linearizable special cases of the QAP
• Two classes of quadratic assignment problems that are solvable as linear assignment problems
• A branch-and-cut algorithm for quadratic assignment problems based on linearizations
• A linear time algorithm for the Koopmans-Beckmann QAP linearization and related problems
• A characterization of linearizable instances of the quadratic minimum spanning tree problem
• Special cases of the quadratic shortest path problem
• The quadratic shortest path problem: complexity, approximability, and solution methods
• The linearization problem of a binary quadratic problem and its applications
• The quadratic cycle cover problem: special cases and efficient bounds
• Linearizable special cases of the quadratic shortest path problem
• An O(n⁴) Algorithm for the QAP Linearization Problem
• A contribution to quadratic assignment problems
• On Solving the Quadratic Shortest Path Problem
• A Mean-Variance Model for Route Guidance in Advanced Traveler Information Systems
• The Variance-Constrained Shortest Path Problem

This page was built for publication: A linear time algorithm for linearizing quadratic and higher-order shortest path problems