k-Best Solutions under Distance Constraints in Valuated -Matroids |
| |
Authors: | Ingo Althfer Walter Wenzel |
| |
Institution: | aFriedrich-Schiller-Universität Jena, Fakultät Mathematik und Informatik, 07740, Jena, Germanyf1;bTechnische Universität Chemnitz Fakultät für Mathematik, 09707, Chemnitz, Germanyf2 |
| |
Abstract: | In discrete maximization problems one usually wants to find an optimal solution. However, in several topics like “alignments,” “automatic speech recognition,” and “computer chess” people are interested to find thekbest solutions for somek ≥ 2. We demand that theksolutions obey certain distance constraints to avoid that thekalternatives are too similar. Several results for valuated -matroids are presented, some of them concerning time complexity of algorithms. |
| |
Keywords: | Discrete optimization k-best algorithms the Greedy algorithm (valuated) matroids (valuated) -matroids distance constraints convexity in graphs |
本文献已被 ScienceDirect 等数据库收录! |
|