@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.