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
Counterexamples to Wegner's Conjecture for Rectangles
Deepak Ajwani, Rishikesh Gajjala, Rajiv Raman +1
Wegner conjectured in 1965 that every finite family of axis-parallel rectangles satisfies , where is the minimum…