Decomposing permutations via cost-constrained transpositions

Farzad Farnoud, Olgica Milenkovic

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publication2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011
Pages2095-2099
Number of pages5
DOIs
StatePublished - Oct 26 2011
Event2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011 - St. Petersburg, Russian Federation
Duration: Jul 31 2011Aug 5 2011

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
ISSN (Print)2157-8104

Other

Other2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011
CountryRussian Federation
CitySt. Petersburg
Period7/31/118/5/11

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Information Systems
  • Modeling and Simulation
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Decomposing permutations via cost-constrained transpositions'. Together they form a unique fingerprint.

Cite this