Two-Best Solutions under Distance Constraints: The Model and Exemplary Results for Matroids

AbstractIn discrete maximization problems one typically wants to find an optimal solution. However, in topics like “alignment of DNA-strings,” “automatic speech recognition,” and “computer chess” people have been asking for finding not only the best, but thekbest solutions. Sometimes it becomes a problem when thesekbest solutions are too similar. This similarity problem may be overcome by demanding that theksolutions obey certain distance conditions. We investigate the simplest casek=2 and we look at valuated matroids. We present several exemplary results, concerning also time complexity. These results are interesting in themselves. But they are also good references for similar studies in other fields with less smooth structures