论文标题
对于精确性条件的词典瓶颈分配问题的一种贪婪且可分发的方法
A Greedy and Distributable Approach to the Lexicographic Bottleneck Assignment Problem with Conditions on Exactness
论文作者
论文摘要
解决词典瓶颈分配问题（LEXBAP）通常依赖于以四分之一的复杂性来进行集中计算。我们考虑顺序瓶颈分配问题（SEQBAP），该问题为LexBap提供了贪婪的解决方案，并讨论了Seqbap，LexBap和瓶颈分配问题（BAP）之间的关系。特别是，我们重新检查了用于分析BAP结构的工具，并将其应用于以立方复杂性解决SEQBAP的算法。我们表明，LexBAP的解决方案集是SEQBAP解决方案的子集，并分析了解决方案集相同的条件。此外，我们提供了一种验证这些条件满意度的方法。在满足条件的情况下，求解SEQBAP的提出算法通过具有较低复杂性并且可以在计算剂网络上分布的计算来解决LEXBAP。通过将移动机器人分配给目标位置的案例研究证明了该方法的适用性。
Solving the Lexicographic Bottleneck Assignment Problem (LexBAP) typically relies on centralised computation with order quartic complexity. We consider the Sequential Bottleneck Assignment Problem (SeqBAP), which yields a greedy solution to the LexBAP and discuss the relationship between the SeqBAP, the LexBAP, and the Bottleneck Assignment Problem (BAP). In particular, we reexamine tools used to analyse the structure of the BAP, and apply them to derive an algorithm that solves the SeqBAP with cubic complexity. We show that the set of solutions of the LexBAP is a subset of the solutions of the SeqBAP and analyse the conditions for which the solutions sets are identical. Furthermore, we provide a method to verify the satisfaction of these conditions. In cases where the conditions are satisfied, the proposed algorithm for solving the SeqBAP solves the LexBAP with computation that has lower complexity and can be distributed over a network of computing agents. The applicability of the approach is demonstrated with a case study where mobile robots are assigned to goal locations.
