Shifting is Optimal under Gap-ETH: A Lower Bound Framework for Geometric Approximation Schemes
It provides tight conditional lower bounds for geometric approximation schemes, confirming optimality of known algorithms for practitioners.
The paper proves that the running times of PTASes based on the shifting technique are optimal under Gap-ETH for any constant dimension, covering problems like maximum independent set on unit ball graphs and piercing unit balls.
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 $d$-dimensional 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 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.