A lot of Geometric Optimization problems are NP-hard and APX-hard to approximate (No PTAS unless P=NP). One example of the geometric set cover problem can be found here. However, it is not easy to prove the lower bound (or inapproximability results) even we know a constant approximation ratio exists.

Khot showed the connection of UGC and Certain problems in geometry, especially related to isoperimetry and embeddings between metric spaces and their inapproximability results.

Guruswami et al. showed bypassing UGC from Some Optimal Geometric Inapproximability Results.

The recent breakthroughs for UGC improve a lot of inapproximability results such as Set Cover. However, I didn't find their connections with geometric optimization problems.

What are the inapproximability results for APX-hard geometric optimization problems such as geometric set cover, geometric hitting set etc. ?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy