Shifting is Optimal under Gap-ETH: A Lower Bound Framework for Geometric Approximation Schemes

Jul 16, 2026

Upload by Oliver

Shifting algorithms of Hochbaum and Maass yield PTASes with the fastest known running times nO(1/εd−1) for many d-dimensional geometric optimization problems. It was only known that these runtimes are optimal for d=2; this work proves conditional optimality under Gap-ETH for every constant dimension. A general lower-bound framework is presented for unit ball graphs including maximum independent set, maximum induced forest, and piercing unit balls, built from the cube wiring theorem and reduction techniques.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages40

Reading Time1 h 41 min

AccessFree to download

Introduction

PTAS/EPTAS running-time optimization and lower bounds

Shifting technique overview

Question on optimality for higher dimensions

Matrix Tiling as a candidate reduction base

arXiv :2607 .06069v 1 [ cs .CG] 7 Jul 2026 Shifting is Optimal under Gap-ETH: A Lower Bound Framework for Geometric Approximation Schemes Manuel Cáceres∗ Sándor Kisfaludi-Bak† Saeed Odak† Abstract The shifting technique of Hochbaum and Maass [J.ACM’85] produces PTASes with the fastest known running times nO(1/ε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. 1 Introduction One of the great successes in the area of geometric algorithms is the existence of polynomial-time approximation schemes (PTASes) in low-dimensional settings. The resulting running times are usually of the form 2f(1/ε)poly(n) or nf(1/ε) . The former are called efficient polynomial time approximation schemes, or EPTAS for short. Once a PTAS or EPTAS running time is achieved for a problem, the research focuses on optimizing the dependence on n and 1/ε until a matching (conditional) lower bound is proven. The first technique for proving EPTAS and PTAS lower bounds was introduced by Marx [26] . Under the Exponential Time Hypothesis (ETH) [18], Marx provided almost matching lower bounds for several problems on planar graphs and on intersection graphs of unit disks: for maximum independent set, the running times 2O(1/ε)poly(n) in planar graphs and nO(1/ε) in unit disk graphs are essentially optimal. Using the stronger Gap-ETH hypothesis [14 , 24], Marx’s techniques give tight lower bounds: they match up to constant factors in the exponent. However, the technique does not extend to higher-dimensional geometric problems. In dimension 3 and above, a lower bound framework was devised by De Berg et al. [12] for exact algorithms. These results can be extended by using their Cube Wiring Theorem (see also [20]) and a careful analysis of gaps, to obtain lower bounds of the form 2Ω(1/εd−1) poly(n) under Gap-ETH, in particular for the Euclidean traveling salesman problem [22] . The same technique has been used recently for proving EPTAS lower bounds for clustering problems [9] . This higher-dimensional lower bound technique only produces lower bounds of the form 2Ω(1/εd−1) poly(n) . Currently, there is no technique that yields lower bounds of the form nΩ(1/εd−1) . On the other hand, the shifting technique of Hochbaum and Maass [17] is a common source of such running times. Shifting is a simple meta-algorithm that can be sketched as follows. Consider a randomly shifted grid consisting of hypercube cells of side length O(1/ε) . Obtain a naive ∗ Department of Computer Science, Aalto University, Finland and Department of Mathematics and Computer Science, University of Southern Denmark, Denmark. Research supported by the Helsinki Institute for Information Technology HIIT. †Department of Computer Science, Aalto University, Espoo, Finland. Research supported by the Research Council of Finland, Grant 363444 . solution near the boundary of the cells. Due to the random shift, any given constant size ball has a probability of at most Od(ε) of being intersected by a cell boundary, thus in expectation the naive solution introduces an error of at most Od(ε · opt) . Additionally, the remaining instancesin the interiors of the cells are pairwise disjoint and do not interfere, thus they can be solved separately. Each such instance has a volume of O(1/εd

FAQs

What does the paper prove about shifting algorithms under Gap-ETH?

It proves that the running times of shifting-based PTAS algorithms are conditionally optimal under Gap-ETH for every constant dimension, extending known optimality beyond d=2.

Which geometric problems on unit ball graphs are covered by the framework?

The framework supports conditional optimality proofs for problems such as maximum independent set, maximum induced forest, and piercing unit balls on unit ball graphs.

How is the lower-bound framework constructed?

It combines the cube wiring theorem by De Berg et al. with reduction steps from Marx and Sidiropoulos to form a maximization-style geometric CSP that serves as a reduction basis.

Jul 16, 2026

Upload by Oliver