In this thesis, the minimax linear placement problem which minimizes the maximum number of interboard connections in a large system is considered. A solution for this problem has various applications of modern printing circuit board layout and LSI techniques.
Three strategies, breaking ties, selecting an initial board from every input board and iterative improvement, are considered to improve C-ALGORITHM, proposed in [10], for obtaining an approximate solution for this problem. Several algorithms given by the combinations of the above three strategies are programmed and tested. It has been found that as O($mn^2$)-algorithm, Q-A-T-ALGORITHM using the tie breaking strategy and the iterative improvement strategy shows the best practical performance and as O($m^2n^2$,$mn^3$)-algorithm, A-T-ALL-ALGORITHM using all the above three strategies shows the best practical performance.
본 논문에서는, 대형 시스템내의 각 MODULE 사이로 지나가는 선의 최대 수들 최소화하는 minimax linear placement 문제에 대해서 고려했다. 이 문제를 해결하는 효율적인 알고리듬은 PCB layout, LSI 제작 등 여러 분야에 적용될 수 있다. Goto, Cederbaum, Ting 이 이 문제를 해결하기 위하여 제안한 approximation 알고리듬인 C-ALGORITHM 을 개선하기 위해서 tie breaking 방법, initial board selecting 방법 그리고 iterative improvement 방법 등이 본 논문에서 제시되었고 이 방법들을 조합해서 여러 알고리듬들이 만들어지고 program 되어서 검토되었다. 그 결과 $O(mn^2)$-algorithm 들 중에서는 tie breaking 방법과 iterative improvement 방법을 사용하는 Q-A-T-ALGORITHM 이, O($m^2n^2$,$mn^3$)-algorithm 으로서 위 세 방법을 모두 사용하는 A-T-ALL-ALGORITHM 이 가장 좋은 것으로 나타났다.
