@article{ART002064512},
author={Sang-Un, Lee},
title={One-Sided Optimal Assignment and Swap Algorithm for Two-Sided Optimization of Assignment Problem},
journal={Journal of The Korea Society of Computer and Information},
issn={1598-849X},
year={2015},
volume={20},
number={12},
pages={75-82}
TY - JOUR
AU - Sang-Un, Lee
TI - One-Sided Optimal Assignment and Swap Algorithm for Two-Sided Optimization of Assignment Problem
JO - Journal of The Korea Society of Computer and Information
PY - 2015
VL - 20
IS - 12
PB - The Korean Society Of Computer And Information
SP - 75
EP - 82
SN - 1598-849X
AB - Generally, the optimal solution of assignment problem can be obtained by Hungarian algorithm of two-sided optimization with time complexity O(n4) . This paper suggests one-sided optimal assignment and swap optimization algorithm with time complexity O(n2) can be achieve the goal of two-sided optimization. This algorithm selects the minimum cost for each row, and reassigns over-assigned to under-assigned cell. Next, that verifies the existence of swap optimization candidates, and swap optimizes with k-opt (k=2,3) . For 27 experimental data, the swap-optimization performs only 22% of data, and 78% of data can be get the two-sided optimal result through one-sided optimal result.
Also, that can be improves on the solution of best known solution for partial problems.
KW - Hungarian Algorithm;Minimum Cost;One-sided Optimization;Reassignment;Swap
DO -
UR -
ER -
Sang-Un, Lee. (2015). One-Sided Optimal Assignment and Swap Algorithm for Two-Sided Optimization of Assignment Problem. Journal of The Korea Society of Computer and Information, 20(12), 75-82.
Sang-Un, Lee. 2015, "One-Sided Optimal Assignment and Swap Algorithm for Two-Sided Optimization of Assignment Problem", Journal of The Korea Society of Computer and Information, vol.20, no.12 pp.75-82.
Sang-Un, Lee "One-Sided Optimal Assignment and Swap Algorithm for Two-Sided Optimization of Assignment Problem" Journal of The Korea Society of Computer and Information 20.12 pp.75-82 (2015) : 75.
Sang-Un, Lee. One-Sided Optimal Assignment and Swap Algorithm for Two-Sided Optimization of Assignment Problem. 2015; 20(12), 75-82.
Sang-Un, Lee. "One-Sided Optimal Assignment and Swap Algorithm for Two-Sided Optimization of Assignment Problem" Journal of The Korea Society of Computer and Information 20, no.12 (2015) : 75-82.
Sang-Un, Lee. One-Sided Optimal Assignment and Swap Algorithm for Two-Sided Optimization of Assignment Problem. Journal of The Korea Society of Computer and Information, 20(12), 75-82.
Sang-Un, Lee. One-Sided Optimal Assignment and Swap Algorithm for Two-Sided Optimization of Assignment Problem. Journal of The Korea Society of Computer and Information. 2015; 20(12) 75-82.
Sang-Un, Lee. One-Sided Optimal Assignment and Swap Algorithm for Two-Sided Optimization of Assignment Problem. 2015; 20(12), 75-82.
Sang-Un, Lee. "One-Sided Optimal Assignment and Swap Algorithm for Two-Sided Optimization of Assignment Problem" Journal of The Korea Society of Computer and Information 20, no.12 (2015) : 75-82.
