TY - GEN

T1 - Decomposing permutations via cost-constrained transpositions

AU - Farnoud, Farzad

AU - Milenkovic, Olgica

PY - 2011/10/26

Y1 - 2011/10/26

N2 - We consider the problem of finding the minimum cost transposition decomposition of a permutation. In this framework, arbitrary non-negative costs are assigned to individual transpositions and the task at hand is to devise polynomial-time, constant-approximation decomposition algorithms. We describe a polynomial-time algorithm based on specialized search strategies that constructs the optimal decomposition of individual transpositions. The analysis of the optimality of decompositions of single transpositions uses graphical models and Menger's theorem. We also present a dynamic programing algorithms that finds the minimum cost, minimum length decomposition of a cycle and show that this decomposition represents a 4-approximation of the optimal solution. The results presented for individual cycles extend to general permutations.

AB - We consider the problem of finding the minimum cost transposition decomposition of a permutation. In this framework, arbitrary non-negative costs are assigned to individual transpositions and the task at hand is to devise polynomial-time, constant-approximation decomposition algorithms. We describe a polynomial-time algorithm based on specialized search strategies that constructs the optimal decomposition of individual transpositions. The analysis of the optimality of decompositions of single transpositions uses graphical models and Menger's theorem. We also present a dynamic programing algorithms that finds the minimum cost, minimum length decomposition of a cycle and show that this decomposition represents a 4-approximation of the optimal solution. The results presented for individual cycles extend to general permutations.

UR - http://www.scopus.com/inward/record.url?scp=80054820082&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=80054820082&partnerID=8YFLogxK

U2 - 10.1109/ISIT.2011.6033925

DO - 10.1109/ISIT.2011.6033925

M3 - Conference contribution

AN - SCOPUS:80054820082

SN - 9781457705953

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 2095

EP - 2099

BT - 2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011

T2 - 2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011

Y2 - 31 July 2011 through 5 August 2011

ER -