The limited blessing of low dimensionality

DOI10.1145/2582112.2582124zbMATH Open1395.68309arXiv1612.01171OpenAlexW2022459721MaRDI QIDQ4635529

Author name not available (Why is that?)

Publication date: 23 April 2018

Published in: (Search for Journal in Brave)

Abstract: We are studying $d$-dimensional geometric problems that have algorithms with $1-1/d$ appearing in the exponent of the running time, for example, in the form of $2^{n^{1-1/d}}$ or $n^{k^{1-1/d}}$. This means that these algorithms perform somewhat better in low dimensions, but the running time is almost the same r all large values $d$ of the dimension. Our main result is showing that for some of these problems the dependence on $1-1/d$ is best possible under a standard complexity assumption. We show that, assuming the Exponential Time Hypothesis, --- $d$-dimensional Euclidean TSP on $n$ points cannot be solved in time $2^{O(n^{1-1/d-epsilon})}$ for any $epsilon>0$, and --- the problem of finding a set of $k$ pairwise nonintersecting $d$-dimensional unit balls/axis parallel unit cubes cannot be solved in time $f(k)n^{o(k^{1-1/d})}$ for any computable function $f$. These lower bounds essentially match the known algorithms for these problems. To obtain these results, we first prove lower bounds on the complexity of Constraint Satisfaction Problems (CSPs) whose constraint graphs are $d$-dimensional grids. We state the complexity results on CSPs in a way to make them convenient starting points for problem-specific reductions to particular $d$-dimensional geometric problems and to be reusable in the future for further results of similar flavor.

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

Mathematics Subject Classification ID

No records found.

This page was built for publication: The limited blessing of low dimensionality

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4635529)