Problems with Random Problems
Do Understand Your Problem Generator
- Constraint satisfaction provides an undying example
- 40+ papers over 5 years by many authors
- used random problems from “Models A, B, C, D”
- All four models were “flawed”
- Achlioptas et al, 1997
- asymptotically almost all problems are trivial
- brings into doubt many experimental results
- some experiments at typical sizes affected
- fortunately not many
- How should we generate problems in future
-
-
-