17 Feb
2016
17 Feb
'16
8:02 a.m.
Does anyone have a favorite example of a fake optimum? One class of examples that comes to mind is certain packing problems, where the constraints all obey some sort of symmetry but the optimal symmetrical solution is not as good as the optimal asymmetrical solution. I'm especially interested in optimization problems where a greedy approach seems intuitively optimal but isn't. E.g., try to construct the biggest possible subset of {1,2,...,20} in which no two elements differ by 3 or 5. A greedy construction gives {1,2,3,9,10,11,17,18,19}, but this isn't optimal. (Yes, this is for my blog. My default is to give credit to contributors, so if you prefer anonymity, please let me know!) Jim