3-4-cyclefree(n)
Search for simple graphs on n vertices that contain neither a 3-cycle nor a 4-cycle, while maximizing the number of edges. The section "H={C₃, C₄}" of Extremal Graphs and Turan numbers lists known computational lower bounds.Gasoline
[Todo: Define the problem and improve this description] This is a combinatorial optimization problem. There exists an approximation algorithm whose exact approximation-ratio is unknown, but exceeds at least 2. Specifically, for any ε>0, there exists an instance of the problem where the solution found by the algorithm is at least (2-ε)-times worse than the optimal solution.
FunSearch does not search for a function that yields a good solution, but instead tries to find an instance of the problem that has a bad (i.e. high) approximation-ratio.
Generalised Gasoline
[Todo: Define the problem and improve this description]
Paging
Search for an online-heuristic for the page-replacement-problem.Clustering: Greedy K-Means Approximation-Ratio
Find instances of the k-means-clustering-problem for which the clustering found by the greedy algorithm has a high cost relative to the optimal clustering. The approximation-ratio of an instance is the maximum of the approximation-ratios across each possible value of k.Weighted K-Means
In this generalisation, each point has a non-negative weight. The distance from a center c to a point p is the usual distance (the square of the euclidean distance) between c and p, but multiplied by the weight of p. When using integer (or, by extension, rational) weights, this shouldn't lose generality, because a point with weight z can be replaced with z identical points of weight 1.Clustering: Price of K-Median Hierarchy
Find instances of the discrete k-median-clustering-problem for which the optimal hierarchical clustering has a high price-of-hierarchy.
The price-of-hierarchy of an instance is the lowest cost-ratio of any hierarchical clustering of that instance. The cost-ratio of a hierarchical clustering is the maximum of the cost-ratios across all its levels. The cost-ratio of level k is the total cost of the hierarchy's clustering on that level, divided by the optimal cost of a k-clustering.