An efficient algorithm for on-line searching of minima in Monge path-decomposable tridimensional arrays
From MaRDI portal
Publication:293394
DOI10.1016/S0020-0190(98)00137-9zbMath1339.68115MaRDI QIDQ293394
Pedro Jodrá, F. Javier Tejel, Alfredo Daniel Garcia
Publication date: 9 June 2016
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0020-0190(98)00137-9
computational complexity; traveling salesman problem; computational geometry; Monge matrices: dynamic programming
68Q25: Analysis of algorithms and problem complexity
90C27: Combinatorial optimization
90C39: Dynamic programming
68U05: Computer graphics; computational geometry (digital and algorithmic aspects)
68W27: Online algorithms; streaming algorithms
Related Items
A note on the traveling repairman problem, Computing a Hamiltonian path of minimum Euclidean length inside a simple polygon
Cites Work
- Geometric applications of a matrix-searching algorithm
- A special case of the \(n\)-vertex traveling-salesman problem that can be solved in O(\(n\)) time
- The convex-hull-and-line traveling salesman problem: A solvable case
- Perspectives of Monge properties in optimization
- Efficient special case algorithms for the n-line planar traveling salesman problem
- Improved Algorithms for Economic Lot Size Problems
- On-line dynamic programming with applications to the prediction of RNA secondary structure