approximation algorithms 1geometric stabbing 1hardness of approximation 1lp rounding 1unique games conjecture 1
From the 1 of 2 linked papers with an AI index.
2 papers
cs.CG2026
Tight UGC Thresholds for Geometric Stabbing Problems
Khaled Elbassioni, Rishikesh Gajjala, Saurabh Ray
The paper proves tight hardness thresholds under the Unique Games Conjecture for several geometric stabbing problems by linking integrality‑gap instances of covering LPs to matchin…
cs.CG2026
A Deterministic Bicriteria Approximation Algorithm for the Art Gallery Problem
Khaled Elbassioni
Given a polygon in the plane, the art gallery problem calls for fining the smallest set of points in from which every other point in is seen. We give a deterministic al…