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?

  • 2
    $\begingroup$ What approach is best strongly depends on your problem, your question seems a bit general as-is. Have you looked into local search approaches such as simulated annealing or evolutionary algorithms? $\endgroup$ – Tom van der Zanden Oct 19 '15 at 13:21
  • $\begingroup$ Agree with your comment, it's a bit a philosophical. I'm interested more in what are the use cases when we can use data to draw some conclusions of the performance of designed algorithms. For example, knowing the distribution of the degrees how can we justify the solution for graph problems. $\endgroup$ – novadiva Oct 19 '15 at 13:40
  • 5
    $\begingroup$ Have a look at Dealing with intractability: NP-complete problems. For instance, you can try modeling your problem as an instance of SAT. $\endgroup$ – Juho Oct 19 '15 at 14:44
  • $\begingroup$ This looks like a duplicate of Dealing with intractability: NP-complete problems to me. Can you give any reason why it is not? If so, I suggest you edit the question to show what research you've done, what approaches you've considered, and why you've rejected them (including everything listed there). Alternatively, you might want to edit your question to specify the particular problem you have and ask about that specific problem. $\endgroup$ – D.W. Oct 19 '15 at 19:34
  • $\begingroup$ I don't think this is a duplicate, as this question is more specific ("designing a heuristic" rather than "how can I deal with it") than the duplicate. The duplicate is quite possibly too broad. $\endgroup$ – Tom van der Zanden Jul 12 '16 at 14:19

Your Answer

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

Browse other questions tagged or ask your own question.