Pith. sign in

REVIEW 2 major objections 7 minor 29 references

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

T0 review · 2 major / 7 minor · reviewed 2026-07-08 · glm-5.2

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Shifting proved optimal for geometric approximation in every dimension

desk verdict Shifting PTAS lower bounds extended to all constant dimensions — solid framework, worth a serious referee read the letter →

arxiv 2607.06069 v1 pith:5PDKFDE5 submitted 2026-07-07 cs.CG

Manuel Cáceres , Sándor Kisfaludi-Bak , Saeed Odak This is my paper · ORCID
classification cs.CG
keywords frameworkgeometricoptimalshiftingalgorithmsdimensiongap-ethknown
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper proves that the classical shifting technique of Hochbaum and Maass produces the fastest possible polynomial-time approximation schemes for a range of geometric problems on unit ball graphs in every fixed dimension d >= 2, assuming Gap-ETH. Previously, this optimality was known only for d=2 (due to Marx, FOCS 2007). The authors develop a lower-bound framework built on a chain of gap-preserving reductions: starting from Max-(3,3)-SAT, they embed the formula's incidence graph into a d-dimensional grid using the Cube Wiring Theorem, construct a geometric CSP instance whose variables encode wire values in small grid cubes, and then reduce through Projection CSP, TilingCSP, and <=-CSP to reach target problems. The framework yields matching upper and lower bounds of n^{O(1/epsilon^{d-1})} for Maximum Independent Set, Minimum Dominating Set, Maximum Induced Forest, Maximum Induced Matching, and Minimum Piercing Set on unit ball graphs in R^d. The key structural insight is that the wire-cube intersection locality ensures that a constant fraction of violated clauses in the original formula propagates proportionally to a constant fraction of violated CSP constraints, preserving the gap through every reduction step.

What carries the argument

The reduction chain proceeds through five stages: (1) Max-(3,3)-SAT to Max-GeometricCSP via Cube Wiring embedding with wire-cube encoding; (2) Max-GeometricCSP to Max-ProjectionCSP via the Marx-Sidiropoulos construction with a charging scheme showing each constraint is charged at most O(3^d) times; (3) Max-ProjectionCSP to Max-<=-CSP via cycle gadgets with 12 variables per original variable; (4) Max-ProjectionCSP to Max-TilingCSP by replacing inequality constraints with equality constraints; (5) Max-TilingCSP or Max-<=-CSP to each target geometric problem via problem-specific gadget constructions. The shifting upper bound uses a randomly shifted grid of side length O(1/epsilon), where each d

What would settle it

A PTAS for Maximum Independent Set (or any of the other four problems) on unit ball graphs in R^d for some fixed d >= 3 running in time n^{o(1/epsilon^{d-1})} would contradict Gap-ETH if the paper's reduction chain is correct. Conversely, a flaw in the gap-preservation argument at any stage of the reduction chain would weaken or invalidate the lower bound.

Watch

Extended reading notes

Core claim

The central discovery is a gap-preserving reduction chain from Max-(3,3)-SAT to geometric constraint satisfaction problems on d-dimensional grids, where the Cube Wiring Theorem embeds the formula incidence graph using vertex-disjoint wires, and each grid cube's variable encodes the Boolean values of the at most kappa = 6d * s^{d-1} wires passing through it. This locality structure ensures that each violated CSP constraint corrupts at most 6kappa clauses, so the gap propagates with the parameter choice epsilon = delta * s * c_d / n^{1/(d-1)} and s = Omega(log^{1/(d-1)} n). The resulting hardness for Max-TilingCSP and Max-<=-CSP (Theorem 1) then transfers to five geometric problems via problem

Load-bearing premise

The gap-preserving property of the reduction from Max-(3,3)-SAT to Max-GeometricCSP relies on the claim that each violated CSP constraint causes at most 6kappa violated clauses in the original formula, which depends on the wire-cube intersection structure: each small cube intersects at most kappa = 6d * s^{d-1} wires, and each wire corresponds to a literal appearing in at most 3 clauses. If the gap amplification is not tight enough at any step in the reduction chain, the n^{1

Editorial extensions

If this is right

  • Any new PTAS for geometric problems on unit ball graphs in R^d with running time n^{O(1/epsilon^{d-1})} is now conditionally optimal under Gap-ETH, closing the gap between upper and lower bounds for the five problems studied.
  • The framework can be applied to other geometric problems on unit ball or unit cube intersection graphs by constructing gap-preserving reductions from Max-TilingCSP or Max-<=-CSP, following the pattern established by the five applications.
  • The distinction between EPTAS lower bounds (2^{Omega(1/epsilon^{d-1})} form) and PTAS lower bounds (n^{Omega(1/epsilon^{d-1})} form) is now bridged for these geometric problems, showing that the n^{1/epsilon^{d-1}} dependence is inherent and not an artifact of the shifting technique.
  • The new gadget constructions for Maximum Induced Forest and Maximum Induced Matching, which use private balls to enforce clique exclusivity and a global forest to enforce disjointness of consecutive selections, provide reusable templates for proving hardness of other induced substructure problems.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The framework likely extends to other problems on intersection graphs of fat objects (e.g., unit squares, unit cubes, pseudo-disks) in fixed dimension, since the shifting upper bound and the reduction gadgets depend primarily on the intersection geometry of congruent fat objects.
  • If Gap-ETH is weakened to ETH, the lower bound degrades from n^{Omega(1/epsilon^{d-1})} to 2^{Omega(1/epsilon^{d-1})} * poly(n), matching the EPTAS lower bound regime; the tightness of the PTAS lower bound specifically requires the gap amplification that Gap-ETH provides.
  • The parameter s = Omega(log^{1/(d-1)} n) in the reduction suggests a natural trade-off between the wire density per cube and the formula size; this could connect to separator-based exact algorithms where the O(1/epsilon^{d-1}) separator size arises from the same dimensional geometry.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 7 minor

Summary. This paper establishes that the shifting technique of Hochbaum and Maass yields optimal PTAS running times (of the form n^{O(1/ε^{d-1})}) for several geometric problems on unit ball graphs in R^d, under Gap-ETH, for every constant dimension d ≥ 2. The framework proceeds by constructing a gap-preserving reduction chain from Max-(3,3)-SAT through GeometricCSP, ProjectionCSP, ≤-CSP, and TilingCSP (Theorem 1), using the Cube Wiring Theorem of De Berg et al. and reduction steps from Marx–Sidiropoulos. The authors then apply this framework to Maximum Independent Set, Minimum Dominating Set, Maximum Induced Forest, Maximum Induced Matching, and Minimum Piercing Set (Theorem 2), providing matching upper bounds via shifting for the latter three. The new gadget constructions for Maximum Induced Forest and Maximum Induced Matching are the main technical contributions beyond the framework itself.

Significance. The paper resolves a natural and explicitly stated open question (Question 1) about the optimality of shifting-based PTASes in dimensions d ≥ 3. The gap-preserving reduction chain from Gap-ETH to TilingCSP/≤-CSP with the n^{Ω(1/ε^{d-1})} lower bound is the central contribution and appears sound. The new gadget for Maximum Induced Forest (Theorem 14), with its global forest structure, private balls, and cycle-creation argument, is a non-trivial adaptation of Marx's independent-set gadget and is likely of independent interest. The matching upper bounds for Maximum Induced Forest, Maximum Induced Matching, and Minimum Piercing Set via shifting and separator-based exact subroutines round out the contribution. The black-box use of the Blank et al. k-center gadgetry for Minimum Piercing Set is appropriate.

major comments (2)
  1. §5.2, Theorem 14, Claim 15 (p. 18): The proof of Claim 15 establishes the cyclic ordering property for consecutive clique positions on the *same side* of Q_v, where the directional vector d is shared. However, at corner positions (where d_j and d'_{j+1} are perpendicular), the distance calculation changes because consecutive positions lie on different sides of the square. The proof states the corner case uses perturbation ι(s)ρ(d_j + d'_{j+1}), but the distance analysis for whether balls at corner-adjacent positions intersect or are disjoint is not explicitly verified. Since the cyclic ordering argument requires the property to hold at *every* consecutive pair around the entire cycle (including all four corners), this gap should be addressed with an explicit calculation or a reference to where it is verified.
  2. §5.2, Theorem 14, d ≥ 3 construction (pp. 21–24): The transition from the d = 2 construction to d ≥ 3 via the Hamiltonian cycle on the cross-polytope is described at a high level, but several geometric details that are carefully specified for d = 2 are omitted for d ≥ 3. Specifically: (a) the exact placement of private and forest balls at corner positions along the Hamiltonian cycle (where perpendicular transitions occur) is stated to be feasible due to 'enough room' but without explicit coordinates or distance bounds; (b) the connector chain geometry between gadgets on non-axis-aligned facets is not fully specified. Since the cyclic ordering property (Claim 15) and the connector consistency (Claim 16) are load-bearing for the reduction's correctness, the authors should either provide the missing geometric verification for d ≥ 3 or clearly state that the d = 2 arguments extend verbatim (
minor comments (7)
  1. §3, Theorem 6 proof (p. 10): The text references 'Theorem 7' in two places ('by Theorem 7') where it should reference Claim 7. This is a cross-reference error.
  2. §4.1, Proposition 8 (p. 12): The direction of the inequality |C| ≤ c_d|C'| in the proof appears inconsistent with the charging argument. The text charges each constraint of C' to a constraint of C, with each constraint of C charged at most O(3^d) times, which should give |C'| ≤ c_d|C|. The subsequent argument uses ε/c_d as the fraction, which is consistent with |C'| ≤ c_d|C|, but the stated inequality |C| ≤ c_d|C'| seems reversed.
  3. §5.2, Figure 8 (p. 19): The coordinates listed for t_1 involve a square root expression that is not fully simplified. A cleaner expression or a note that this is the unique point satisfying the tangency condition would improve readability.
  4. §5.5, Theorem 30 (p. 31): The footnote about scaling the point set by 1/(2r_0) to make balls have unit diameter is slightly confusing since the main text already defines unit balls as having diameter 1. Clarifying that the scaling is applied to the output of [5] to match this convention would help.
  5. §6.1, Theorem 36 (p. 35): The alternative approach using P-flattened treewidth is mentioned in a single sentence. A brief citation to the specific theorem in [12] that yields the n^{O(ℓ^{d-1})} bound would make this more verifiable.
  6. Throughout: The notation switches between 'unit ball' (open ball of diameter 1) and 'unit disk' (in the d = 2 case). Using 'unit ball in R^2' consistently, or explicitly stating that 'unit disk' means 'unit ball in R^2', would improve consistency.
  7. §1.1, Figure 2 (p. 5): The reduction chain diagram shows 'Max-≤-CSP' and 'Max-TilingCSP' but the text sometimes refers to these without the 'Max-' prefix. Consistency would help.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and the constructive feedback. The referee has identified two genuine gaps in the geometric verification of our gadget construction for Maximum Induced Forest (Theorem 14). We address both below and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: §5.2, Theorem 14, Claim 15 (p. 18): The proof of Claim 15 establishes the cyclic ordering property for consecutive clique positions on the same side of Q_v, where the directional vector d is shared. However, at corner positions (where d_j and d'_{j+1} are perpendicular), the distance calculation changes because consecutive positions lie on different sides of the square. The proof states the corner case uses perturbation ι(s)ρ(d_j + d'_{j+1}), but the distance analysis for whether balls at corner-adjacent positions intersect or are disjoint is not explicitly verified. Since the cyclic ordering argument requires the property to hold at every consecutive pair around the entire cycle (including all four corners), this gap should be addressed with an explicit calculation or a reference to where it is verified.

    Authors: The referee is correct that the proof of Claim 15 as written only handles the case where consecutive positions p_j and p_{j+1} lie on the same side of Q_v and share a common directional vector d. The corner case—where p_j is the last position on one side and p_{j+1} is the first position on the perpendicular side—requires a separate distance calculation that we omitted. We will add this calculation explicitly in the revised manuscript. The key observation is that at a corner, the two consecutive positions are at unit ℓ_1-distance (they differ in two coordinates, each by 1/2 in the d=2 construction with unit spacing along the boundary), and the perturbation at the corner position is ι(s)ρ(d_j + d'_{j+1}), which has components along both directional vectors. Writing out the squared distance between B_j(v,s) and B_{j+1}(v,s') at a corner, the dominant term is the ℓ_1-distance between p_j and p_{j+1} (which is 1), and the perturbation contributes a correction of order (r'-r)ρ in the relevant direction plus O(Λ^d ρ) in the perpendicular direction. The same inequality chain as in the same-side case applies: if r ≤ r', the distance is at least 1 (disjoint), and if r > r', the distance is strictly less than 1 (intersecting), since 10Λ^{2d}ρ^2 ≪ ρ. We will include this calculation in full in the revision. revision: yes

  2. Referee: §5.2, Theorem 14, d ≥ 3 construction (pp. 21–24): The transition from the d = 2 construction to d ≥ 3 via the Hamiltonian cycle on the cross-polytope is described at a high level, but several geometric details that are carefully specified for d = 2 are omitted for d ≥ 3. Specifically: (a) the exact placement of private and forest balls at corner positions along the Hamiltonian cycle (where perpendicular transitions occur) is stated to be feasible due to 'enough room' but without explicit coordinates or distance bounds; (b) the connector chain geometry between gadgets on non-axis-aligned facets is not fully specified. Since the cyclic ordering property (Claim 15) and the connector consistency (Claim 16) are load-bearing for the reduction's correctness, the authors should either provide the missing geometric verification for d ≥ 3 or clearly state that the d = 2 arguments extend verbatim.

    Authors: The referee raises a valid point. For d ≥ 3, we relied on informal geometric intuition ('enough room') without providing the explicit verification that the referee rightly requests. We will address both sub-points in the revision. For (a), the key difference from d = 2 is that in d ≥ 3, the box Q_v has side length 30 (rather than 11), and the corner positions along the Hamiltonian cycle on the cross-polytope involve transitions between facets whose normals are orthogonal. At each corner position, the private ball is placed in the direction of the outward facet normal, and the forest ball is placed in the direction of the inward normal. Because d ≥ 3 provides an additional dimension orthogonal to both directional vectors d_j and d'_{j+1}, the private and forest balls at corner positions can be displaced into this extra dimension, ensuring they do not create unwanted intersections with balls at non-adjacent positions. We will provide explicit coordinates for the private and forest ball placements at corner positions, analogous to those given in Figure 8 for d = 2, and verify the required intersection properties by direct distance calculation. For (b), the connector chains in d ≥ 3 are always axis-aligned (they connect gadgets along grid edges in direction e_i), so the connector geometry is identical to the d = 2 case—the entry and exit ports on facet F_i (with normal e_i) face the corresponding ports on facet F_{i+d} (with normal -e_i) of the adjacent gadget, and the intermediate clique positions are placed along the e_i direction exactly as in d = 2. We will state this explicitly in the revision and note that Claims 15 and 16 hold verbatim for d ≥ 3 because the connector geometry is unchanged and the corner-position calculation for the cyclic ordering property follows by revision: no

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity found; the reduction chain is self-contained against external benchmarks.

full rationale

The paper's central result (Theorem 2) is a conditional lower bound under Gap-ETH, derived through a reduction chain starting from Max-(3,3)-SAT (an external benchmark) via the Cube Wiring Theorem of De Berg et al. [SICOMP'20] and reduction steps of Marx-Sidiropoulos [SoCG'14]—both externally authored. The paper's main new contributions are: (1) verifying that these external constructions are approximation-preserving (Proposition 8, Theorem 9, Theorem 10), and (2) new gadget constructions for Maximum Induced Forest (Theorem 14), Maximum Induced Matching (Theorem 23), and Minimum Piercing Set (Theorem 31). I traced the full chain: Gap-ETH → Max-(3,3)-SAT (Lemma 3, citing Papadimitriou) → Max-GeometricCSP (Theorem 6, using Cube Wiring Theorem [20]) → Max-ProjectionCSP (Proposition 8, using [27, Prop 2.18]) → Max-≤-CSP/TilingCSP (Theorems 9-10, using [27, Prop 2.19]) → target problems. At each step, the paper explicitly verifies gap preservation through charging arguments (e.g., Claim 7's 6κ bound, Proposition 8's c_d = O(3^d) charging scheme). The self-citations that exist (e.g., [20] is Kisfaludi-Bak's thesis) are used for the Cube Wiring Theorem, which is a geometric construction theorem independent of the approximation results being proved—it does not assume Gap-ETH or any approximation property. The gadget constructions for Maximum Induced Forest and Maximum Induced Matching are genuinely new, with detailed geometric verification (Claims 15-18, 24-26). The Minimum Piercing Set reduction uses [5] (Blank et al., STOC 2026) as a black box with explicitly stated properties (Theorem 30). No step in the chain reduces to its own inputs by construction; each reduction transforms one problem into another with explicit gap analysis. The one minor concern is that [20] shares an author with the present paper, but the Cube Wiring Theorem is a standalone geometric result that does not encode the target conclusion, so this is not load-bearing circularity.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The paper introduces no new mathematical entities, particles, forces, or postulated objects. All problems (TilingCSP, ≤-CSP, GeometricCSP, ProjectionCSP, Binary-SumSet) are either from prior work or natural variants. The gadget constructions (private balls, forest balls, connector chains) are combinatorial objects within standard geometric intersection graphs, not new theoretical entities. Gap-ETH is a standard hypothesis. No free parameters are fitted: the exponent d-1 in the lower bound emerges from the grid dimension and separator size, and the constant γ>0 is existentially quantified (not computed).

assumptions (5)
  • domain assumption Gap-ETH: there exist constants δ,γ>0 such that no 2^{γm}-time algorithm can distinguish satisfiable 3-CNF formulas from those where every assignment violates at least δm clauses.
    Stated in the Preliminaries (Section 2). This is the sole complexity-theoretic hypothesis underlying all lower bounds. It is a standard assumption in fine-grained complexity, not invented by this paper.
  • standard math Strong Cube Wiring Theorem (Theorem 4): for d≥3, any bipartite graph of max degree 2d on n vertices can be embedded in a d-dimensional grid of side Θ(n^{1/(d-1)}) with vertex-disjoint wires.
    Cited from Kisfaludi-Bak [20] / De Berg et al. [12]. Used in Theorem 6 to embed the incidence graph of a (3,3)-CNF formula into the grid. Not proved here.
  • standard math Geometric Separator Theorem (Theorem 35): a set of k unit balls of ply ≤λ in R^d admits a (d-1)-sphere separator with at most O(λ^{1/d}k^{1-1/d}) crossing balls.
    Cited from Miller et al. [28]. Used in Theorem 36 to obtain the n^{O(k^{1-1/d})} exact algorithm for Maximum Induced Forest, which is the subroutine in the shifting PTAS (Theorem 33).
  • domain assumption The construction of Blank et al. [5] (Theorem 30) reduces Binary-SumSet to a geometric covering instance with the stated gap-preserving properties.
    Used as a black box in Section 5.5 for the Minimum Piercing Set lower bound. The properties (i)-(iii) are stated and used but not independently verified in this paper.
  • standard math The reduction steps of Marx and Sidiropoulos [27] (Propositions 2.18 and 2.19) from GeometricCSP to ProjectionCSP and from ProjectionCSP to ≤-CSP preserve satisfiability.
    Used in Sections 4.1-4.2. The paper verifies that these reductions are also approximation-preserving (new contribution), but the constructions themselves are borrowed.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Shifting is Optimal under Gap-ETH: A Lower Bound Framework for Geometric Approximation Schemes." pith.science (2026). https://pith.science/paper/5PDKFDE5

@misc{pith2026260706069,
  author       = {Pith},
  title        = {Pith review of: Shifting is Optimal under Gap-ETH: A Lower Bound Framework for Geometric Approximation Schemes},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5PDKFDE5}},
  note         = {Machine review of arXiv:2607.06069}
}
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 $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.

Figures

Figures reproduced from arXiv: 2607.06069 by the authors.

Figure 1
Figure 1. An instance of Matrix Tiling: the cell assignments are shown in blue; the equality and conflicting assignment on the corresponding coordinates of adjacent cells are shown in green and red respectively. An assignment of I is a function f : V → D. A unary constraint Ca is satisfied by f if f(a) ∈ Ca, and a binary constraint Ca,b is satisfied if (f(a), f(b)) ∈ Ca,b. An assignment is a solution (or satisfying assignment… view at source ↗
Figure 2
Figure 2. Reduction chain used in the proof of Theorem [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. An s-partition of a 2-dimensional embedding of the incidence graph of the formula ϕ = (¯x2 ∨x3 ∨x4)∧(¯x1 ∨x2 ∨x¯4) for s = 6. The wires corresponding to the same variable share the same color. Constructing an instance of Geometric CSP We first define the variables and domain of the Geometric CSP instance. Let s be a positive integer parameter. We define an s-partition of Gd cn1 by grouping vertices into axis-aligned… view at source ↗
Figures from the paper (7 more)
Figure 4
Figure 4. Figure 4: Marx’s gadget [26] for Maximum Independent Set of unit disks via Matrix Tiling. The blue and red disks represent clique positions along the variable gadget and the connector cliques, respectively. Overview of the reduction for Maximum Induced Forest. Our reduction pres…
Figure 5
Figure 5. Figure 5: The vertices corresponding to clique balls (gray regions), forest balls (depicted in [PITH_FULL_IMAGE:figures/full_fig_p017_5.png]
Figure 6
Figure 6. Figure 6: The clique positions along a square of side length [PITH_FULL_IMAGE:figures/full_fig_p018_6.png]
Figure 7
Figure 7. Figure 7: (a) Illustration of the entry chain from entry port position at [PITH_FULL_IMAGE:figures/full_fig_p019_7.png]
Figure 8
Figure 8. Figure 8: Demonstration of relative coordinates of unit disks at the neighborhood of entry port [PITH_FULL_IMAGE:figures/full_fig_p019_8.png]
Figure 9
Figure 9. Figure 9: An instance of unit disks obtained from two adjacent variables of a [PITH_FULL_IMAGE:figures/full_fig_p022_9.png]
Figure 10
Figure 10. Figure 10: Demonstration of the Hamiltonian cycle Hv on the boundary of Qv for d = 3. The corner points u ′ i for i ∈ [6] are represented by small squares. The solid points and squares represent points on the facets F1, F2, and F3, and the empty points and squares represent the …

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

29 extracted references · 29 canonical work pages

  1. [1]

    Agarwal and Cecilia Magdalena Procopiuc

    Pankaj K. Agarwal and Cecilia Magdalena Procopiuc. Exact and approximation algorithms for clustering.Algorithmica, 33(2):201–226, 2002.doi:10.1007/S00453-001-0110-Y

    work page doi:10.1007/s00453-001-0110-y 2002

  2. [2]

    Polynomial Time Approximation Schemes for Euclidean TSP and Other Geometric Problems.Journal of the ACM, 45(5):753–782, 1998.doi:10.1145/290179

    Sanjeev Arora. Polynomial Time Approximation Schemes for Euclidean TSP and Other Geometric Problems.Journal of the ACM, 45(5):753–782, 1998.doi:10.1145/290179. 290180

    work page doi:10.1145/290179 1998

  3. [3]

    Brenda S. Baker. Approximation algorithms for NP-complete problems on planar graphs. Journal of the ACM, 41(1):153–180, 1994.doi:10.1145/174644.174650

    work page doi:10.1145/174644.174650 1994

  4. [4]

    S., and Pasin Manurangsi

    Arnab Bhattacharyya, Suprovat Ghoshal, Karthik C. S., and Pasin Manurangsi. Param- eterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH. In45th International Colloquium on Automata, Languages, and Programming (ICALP), volume 107 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 17:1–17:15, 2018. doi:10.4230/LIPIcs....

    work page doi:10.4230/lipics.icalp.2018.17 2018

  5. [5]

    Proceedings of the 58th ACM Symposium on Theory of Computing , pages =

    Lotte Blank, Karl Bringmann, Parinya Chalermsook, Karthik C. S., Benedikt Kolbe, Hung Le, and Geert van Wordragen. Fine-grained complexity of continuous euclidean k-center. In Aditya Bhaskara and Artur Czumaj, editors,Proceedings of the 58th Annual ACM Sym- posium on Theory of Computing, STOC 2026, Salt Lake City, UT, USA, June 22-26, 2026, pages 330–341....

    work page doi:10.1145/3798129.3800753 2026

  6. [6]

    Édouard Bonnet, Bruno Escoffier, Eun Jung Kim, and Vangelis Th. Paschos. On subex- ponential and FPT-time inapproximability.Algorithmica, 71(3):541–565, 2015.doi: 10.1007/s00453-014-9881-x

    work page doi:10.1007/s00453-014-9881-x 2015

  7. [7]

    Chalermsook, M

    Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manu- rangsi, Danupon Nanongkai, and Luca Trevisan. From gap-exponential time hypothesis to fixed parameter tractable inapproximability: Clique, dominating set, and more.SIAM J. Comput., 49(4):772–810, 2020.doi:10.1137/18M1166869

    work page doi:10.1137/18m1166869 2020

  8. [8]

    Timothy M. Chan. Polynomial-time approximation schemes for packing and piercing fat objects.J. Algorithms, 46(2):178–189, 2003.doi:10.1016/S0196-6774(02)00294-8. 38

    work page doi:10.1016/s0196-6774(02)00294-8 2003

Show all 29 references
  1. [9]

    S., David Saulpic, and Chris Schwiegelshohn

    Vincent Cohen-Addad, Karthik C. S., David Saulpic, and Chris Schwiegelshohn. Almost- optimal upper and lower bounds for clustering in low dimensional euclidean spaces, 2026. arXiv:2603.09846

    2026

  2. [10]

    Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh.Parameterized Algorithms

    Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh.Parameterized Algorithms. Springer, Cham, 2015.doi:10.1007/978-3-319-21275-3

    2015 doi

  3. [11]

    Das, Paz Carmi, and Subhas C

    Minati De, Gautam K. Das, Paz Carmi, and Subhas C. Nandy. Approximation Algorithms for a Variant of discrete Piercing Set Problem for Unit Disks.Int. J. Comput. Geom. Appl., 23(6):461, 2013.doi:10.1142/S021819591350009X

    2013 doi

  4. [12]

    A framework for exponential-time-hypothesis-tight algorithms and lower bounds in geometric intersection graphs.SIAM Journal on Computing, 49(6):1291–1331, 2020

    MarkdeBerg, HansL.Bodlaender, SándorKisfaludi-Bak, DánielMarx, andTomC.vander Zanden. A framework for exponential-time-hypothesis-tight algorithms and lower bounds in geometric intersection graphs.SIAM Journal on Computing, 49(6):1291–1331, 2020. doi:10.1137/18M1167733

    2020 doi

  5. [13]

    Demaine and MohammadTaghi Hajiaghayi

    Erik D. Demaine and MohammadTaghi Hajiaghayi. Bidimensionality: New connections between FPT algorithms and PTASs. InProceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 590–601. SIAM, 2005. URL:https: //dl.acm.org/citation.cfm?id=1070432.1070514

    2005

  6. [14]

    Mildly exponential reduction from gap-3SAT to polynomial-gap label-cover

    Irit Dinur. Mildly exponential reduction from gap-3SAT to polynomial-gap label-cover. Electronic Colloquium on Computational Complexity (ECCC), 23:128, 2016. URL:https: //eccc.weizmann.ac.il/report/2016/128/

    2016

  7. [15]

    S., Euiwoong Lee, and Pasin Manurangsi

    Andreas Emil Feldmann, Karthik C. S., Euiwoong Lee, and Pasin Manurangsi. A survey on approximation in parameterized complexity: Hardness and algorithms.Algorithms, 13(6):146, 2020.doi:10.3390/a13060146

    2020 doi

  8. [16]

    Minimizing average flow-time: Upper and lower bounds

    Naveen Garg and Amit Kumar. Minimizing average flow-time: Upper and lower bounds. In48th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 603–613. IEEE Computer Society, 2007.doi:10.1109/FOCS.2007.52

    2007 doi

  9. [17]

    Hochbaum and Wolfgang Maass

    Dorit S. Hochbaum and Wolfgang Maass. Approximation schemes for covering and packing problems in image processing and VLSI.J. ACM, 32(1):130–136, 1985.doi:10.1145/ 2455.214106

    1985

  10. [18]

    Which problems have strongly exponential complexity?Journal of Computer and System Sciences, 63(4):512–530, 2001

    Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity?Journal of Computer and System Sciences, 63(4):512–530, 2001. doi:10.1006/jcss.2001.1774

    2001 doi

  11. [19]

    Jallu, Prajwal R

    Ramesh K. Jallu, Prajwal R. Prasad, and Gautam K. Das. Minimum Dominating Set for a Point Set inR2.arXiv preprint arXiv:1312.7243, 2014.arXiv:1312.7243

    2014 arXiv

  12. [20]

    Phd the- sis, Technische Universiteit Eindhoven, Department of Mathematics and Computer Sci- ence, Eindhoven, The Netherlands, 2019

    Sándor Kisfaludi-Bak.ETH-tight algorithms for geometric network problems. Phd the- sis, Technische Universiteit Eindhoven, Department of Mathematics and Computer Sci- ence, Eindhoven, The Netherlands, 2019. Available athttps://research.tue.nl/en/ publications/eth-tight-algorit...

    2019

  13. [21]

    van der Zanden

    Sándor Kisfaludi-Bak, Dániel Marx, and Tom C. van der Zanden. How does object fatness impact the complexity of packing in d dimensions? In Pinyan Lu and Guochuan Zhang, editors,30th International Symposium on Algorithms and Computation, ISAAC, LIPIcs, pages 36:1–36:18. Schloss...

    2019

  14. [22]

    A gap-ETH-tight ap- proximation scheme for Euclidean TSP.Journal of the ACM, 72(6):42:1–42:48, 2025

    Sándor Kisfaludi-Bak, Jesper Nederlof, and Karol Węgrzycki. A gap-ETH-tight ap- proximation scheme for Euclidean TSP.Journal of the ACM, 72(6):42:1–42:48, 2025. doi:10.1145/3723180

    2025 doi

  15. [23]

    There is no EPTAS for two-dimensional knapsack.Infor- mation Processing Letters, 110(16):707–710, 2010.doi:10.1016/j.ipl.2010.05.031

    Ariel Kulik and Hadas Shachnai. There is no EPTAS for two-dimensional knapsack.Infor- mation Processing Letters, 110(16):707–710, 2010.doi:10.1016/j.ipl.2010.05.031

    2010 doi

  16. [24]

    A Birthday Repetition Theorem and Com- plexity of Approximating Dense CSPs

    Pasin Manurangsi and Prasad Raghavendra. A Birthday Repetition Theorem and Com- plexity of Approximating Dense CSPs. In44th International Colloquium on Automata, Languages, and Programming (ICALP), pages 78:1–78:15, 2017

    2017

  17. [25]

    Parameterized Complexity of Independence and Domination on Geometric Graphs

    Dániel Marx. Parameterized Complexity of Independence and Domination on Geometric Graphs. In Hans L. Bodlaender and Michael A. Langston, editors,Parameterized and Exact Computation, Second International Workshop, IWPEC, Zürich, Switzerland, September 13- 15, 2006, Proceedings,...

    2006 doi

  18. [26]

    On the optimality of planar and geometric approximation schemes

    Dániel Marx. On the optimality of planar and geometric approximation schemes. In48th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 338–348. IEEE Computer Society, 2007.doi:10.1109/FOCS.2007.26

    2007 doi

  19. [27]

    Thelimitedblessing oflow dimensionality: When 1−1/dis the best possible exponent ford-dimensional geometric problems

    DánielMarxand AnastasiosSidiropoulos. Thelimitedblessing oflow dimensionality: When 1−1/dis the best possible exponent ford-dimensional geometric problems. InProceedings of the 30th Annual Symposium on Computational Geometry (SoCG), pages 67:1–67:10. Association for Computing ...

    2014 doi

  20. [28]

    Miller, Shang-Hua Teng, William P

    Gary L. Miller, Shang-Hua Teng, William P. Thurston, and Stephen A. Vavasis. Separators for sphere-packings and nearest neighbor graphs.J. ACM, 44(1):1–29, 1997.doi:10.1145/ 256292.256294

    1997

  21. [29]

    Papadimitriou.Computational Complexity

    Christos H. Papadimitriou.Computational Complexity. Addison-Wesley, 1994. 40

    1994

Pith tools

Reviewed July 8, 2026 · model on record in the stance chip above.