I have a problem that is NP-hard and even NP-hard to approximate within a factor $n^{1-\varepsilon}$ $\forall \varepsilon > 0$. I'm looking now just for approaches that can help me to design a justifiable solution. I don't need to improve the brute-force solution, I just want to design a heuristic that I can justify somehow. For example, one approach would be to look in real data and try to derive some insights from it: even if don't get a good solution for all types of inputs, maybe it will be good for realistic data. Are there any approaches that can address hard-to-approximate problems? Maybe some papers on the topic?
How to solve a problem that is even hard to approximate?
complexity theory;np hard;approximation;np