Combinatorial optimization problems for which almost every algorithm is asymptotically optimal

Overview & Synopsis

Let Zmax and Zmin be respectively the maximum and minimum of the objective function in a combinatorial problem for which the cardinality of the set of feasible solutions is m and the size of every feasible solution is N. We prove that in a certain probabilistic framework Zmax ~ Zmin almost surely (a.s.) provided log m = o (N) for N and m become large. This result implies that for such a class of combinatorial optimization probblems almost every algorithm finds asymptotically optimal solution. The quadratic assignment problem, the location problem on graphs, and some pattern matching problems fall into this class.