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.
You mean like this one? "Arrange 8 points on the surface of a unit sphere such that the minimum distance between points is as large as possible." There are other optimisation problems like this which are not packing problems per se, such as: "Determine the Steiner tree of four points positioned at the vertices of a square." Or even: "What is the optimal foam of soap bubbles?" (The answer to this one is unknown, but Kelvin's conjecturally optimal foam of truncated octahedra is beaten by the Wieare-Phelan structure.)
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 _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun