The limited blessing of low dimensionality
From MaRDI portal
Publication:4635529
DOI10.1145/2582112.2582124zbMath1395.68309arXiv1612.01171OpenAlexW2022459721MaRDI QIDQ4635529
Dániel Marx, Anastasios Sidiropoulos
Publication date: 23 April 2018
Published in: Proceedings of the thirtieth annual symposium on Computational geometry (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1612.01171
Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (12)
Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams ⋮ The parameterized hardness of the \(k\)-center problem in transportation networks ⋮ The homogeneous broadcast problem in narrow and wide strips. II: Lower bounds ⋮ An ETH-Tight Exact Algorithm for Euclidean TSP ⋮ A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs ⋮ A tight lower bound for edge-disjoint paths on planar DAGs ⋮ Fractal dimension and lower bounds for geometric problems ⋮ On Geometric Set Cover for Orthants ⋮ Unnamed Item ⋮ A Framework for Exponential-Time-Hypothesis--Tight Algorithms and Lower Bounds in Geometric Intersection Graphs ⋮ Subexponential parameterized algorithms for graphs of polynomial growth ⋮ The fine-grained complexity of multi-dimensional ordering properties
This page was built for publication: The limited blessing of low dimensionality