Speeding up dynamic programming in the line-constrained \(k\)-median

DOI10.1007/s00224-017-9780-yzbMath1397.90234OpenAlexW2910609388MaRDI QIDQ726094

Paweł Gawrychowski, Łukasz Zatorski

Publication date: 3 August 2018

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-017-9780-y

zbMATH Keywords

dynamic programming\(k\)-medianMonge propertyline-constraint

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Dynamic programming (90C39) Discrete location and assignment (90B80)

Cites Work

• Unnamed Item
• Unnamed Item
• A linear-time algorithm for concave one-dimensional dynamic programming
• Geometric applications of a matrix-searching algorithm
• The algebraic degree of geometric optimization problems
• Dynamic programming with convexity, concavity and sparsity
• Time bounds for selection
• Line-Constrained $$k$$ -Median, $$k$$ -Means, and $$k$$ -Center Problems in the Plane
• Space-Efficient Data-Analysis Queries on Grids
• On the Complexity of Some Common Geometric Location Problems
• Computing a Minimum Weightk-Link Path in Graphs with the Concave Monge Property

This page was built for publication: Speeding up dynamic programming in the line-constrained \(k\)-median