Shifting is Optimal under Gap-ETH: A Lower Bound Framework for Geometric Approximation Schemes
Jun 26, 2026·
,
,
·
0 min read
Manuel Cáceres
Sándor Kisfaludi-Bak
Saeed Odak
Example of our reduction, for dimension $2$ and formula $\phi = (\bar{x}_2 \lor x_3 \lor x_4) \land (\bar{x}_1 \lor x_2 \lor \bar{x}_4)$
Abstract
The shifting technique of Hochbaum and Maass [J.ACM'85] produces PTASes with the fastest known running times $n^{O(1/\varepsilon^{d-1})}$ for several geometric problems. However, it is only known, due to Marx [FOCS'07], that these algorithms are indeed optimal for dimension $d=2$. We show that these running times are optimal under Gap-ETH for every constant dimension. More precisely, we develop a framework that enables us to prove the conditional optimality of the shifting algorithms for several problems on unit ball graphs, such as maximum independent set, maximum induced forest, and many others, as well as for the problem of piercing unit balls. Our framework is built using the cube wiring theorem of De Berg et al. [SICOMP'20] and the reduction steps of Marx and Sidiropoulos [SoCG'14] to create a convenient maximization version of geometric CSP that can be used as a basis for reductions.
Type
Publication
In ESA 2026
