본문 바로가기
  • Home

An Linear Bottleneck Assignment Problem (LBAP) Algorithm Using the Improving Method of Solution for Linear Minsum Assignment Problem (LSAP)

  • Journal of The Korea Society of Computer and Information
  • Abbr : JKSCI
  • 2016, 21(1), pp.131-138
  • Publisher : The Korean Society Of Computer And Information
  • Research Area : Engineering > Computer Science

Sang-Un, Lee 1

1강릉원주대학교

Accredited

ABSTRACT

In this paper, we propose a simple linear bottleneck assignment problems (LBAP) algorithm to find the optimal solution. Generally, the LBAP has been solved by threshold or augmenting path algorithm. The primary characteristic of proposed algorithm is derived the optimal solution of LBAP from linear sum assignment problem (LSAP). Firstly, we obtains the solution for LSAP from the selected minimum cost of rows and moves the duplicated costs in row to unselected row with minimum increasing cost in direct and indirect paths. Then, we obtain the optimal solution of LBAP according to the maximum cost of LSAP can be move to less cost. For the 29 balanced and 7 unbalanced problem, this algorithm finds optimal solution as simple.

Citation status

* References for papers published after 2022 are currently being built.