| Summary: | The <i>k</i>-assignment problem (or, the <i>k</i>-matching problem) on <i>k</i>-partite graphs is an NP-hard problem for <inline-formula><math display="inline"><semantics><mrow><mi>k</mi><mo>≥</mo><mn>3</mn></mrow></semantics></math></inline-formula>. In this paper we introduce five new heuristics. Two algorithms, <inline-formula><math display="inline"><semantics><msub><mi mathvariant="normal">B</mi><mi>m</mi></msub></semantics></math></inline-formula> and <inline-formula><math display="inline"><semantics><msub><mi mathvariant="normal">C</mi><mi>m</mi></msub></semantics></math></inline-formula>, arise as natural improvements of Algorithm <inline-formula><math display="inline"><semantics><msub><mi mathvariant="normal">A</mi><mi>m</mi></msub></semantics></math></inline-formula> from (He et al., in: Graph Algorithms And Applications 2, World Scientific, 2004). The other three algorithms, <inline-formula><math display="inline"><semantics><msub><mi mathvariant="normal">D</mi><mi>m</mi></msub></semantics></math></inline-formula>, <inline-formula><math display="inline"><semantics><msub><mi mathvariant="normal">E</mi><mi>m</mi></msub></semantics></math></inline-formula>, and <inline-formula><math display="inline"><semantics><msub><mi mathvariant="normal">F</mi><mi>m</mi></msub></semantics></math></inline-formula>, incorporate randomization. Algorithm <inline-formula><math display="inline"><semantics><msub><mi mathvariant="normal">D</mi><mi>m</mi></msub></semantics></math></inline-formula> can be considered as a greedy version of <inline-formula><math display="inline"><semantics><msub><mi mathvariant="normal">B</mi><mi>m</mi></msub></semantics></math></inline-formula>, whereas <inline-formula><math display="inline"><semantics><msub><mi mathvariant="normal">E</mi><mi>m</mi></msub></semantics></math></inline-formula> and <inline-formula><math display="inline"><semantics><msub><mi mathvariant="normal">F</mi><mi>m</mi></msub></semantics></math></inline-formula> are versions of local search algorithm, specialized for the <i>k</i>-matching problem. The algorithms are implemented in Python and are run on three datasets. On the datasets available, all the algorithms clearly outperform Algorithm <inline-formula><math display="inline"><semantics><msub><mi mathvariant="normal">A</mi><mi>m</mi></msub></semantics></math></inline-formula> in terms of solution quality. On the first dataset with known optimal values the average relative error ranges from 1.47% over optimum (algorithm <inline-formula><math display="inline"><semantics><msub><mi mathvariant="normal">A</mi><mi>m</mi></msub></semantics></math></inline-formula>) to 0.08% over optimum (algorithm <inline-formula><math display="inline"><semantics><msub><mi mathvariant="normal">E</mi><mi>m</mi></msub></semantics></math></inline-formula>). On the second dataset with known optimal values the average relative error ranges from 4.41% over optimum (algorithm <inline-formula><math display="inline"><semantics><msub><mi mathvariant="normal">A</mi><mi>m</mi></msub></semantics></math></inline-formula>) to 0.45% over optimum (algorithm <inline-formula><math display="inline"><semantics><msub><mi mathvariant="normal">F</mi><mi>m</mi></msub></semantics></math></inline-formula>). Better quality of solutions demands higher computation times, thus the new algorithms provide a good compromise between quality of solutions and computation time.
|
|---|