Empirical analysis and optimization of an NP−hard problem using CSP and FDR
Andrew C. Simpson · 2007
In many cases where an algorithm is provably NP-hard, this intractability is a worst-case bound that only applies to pathological inputs. In these cases, by exploiting knowledge of the specic structure of \realworld inputs, the algorithm can be shown to be much more ecient in the ormal case. However, when studying a new problem, this can be dicult