Probabilistic analysis of a grouping algorithm |
| |
Authors: | D F Wong and Edward M Reingold |
| |
Affiliation: | (1) Department of Computer Sciences, University of Texas at Austin, 78712 Austin, TX, USA;(2) Department of Computer Science, University of Illinois at Urbana-Champaign, 61801 Urbana, IL, USA |
| |
Abstract: | We study thegrouping by swapping problem, which occurs in memory compaction and in computing the exponential of a matrix. In this problem we are given a sequence ofn numbers drawn from {0,1, 2,...,m–1} with repetitions allowed; we are to rearrange them, using as few swaps of adjacent elements as possible, into an order such that all the like numbers are grouped together. It is known that this problem is NP-hard. We present a probabilistic analysis of a grouping algorithm calledMEDIAN that works by sorting the numbers in the sequence according to their median positions. Our results show that the expected behavior ofMEDIAN is within 10% of optimal and is asymptotically optimal asn/m![rarr](/content/p080l128n5883787/xxlarge8594.gif) or asn/m 0.The work of this author was supported in part by the Texas Advanced Research Program under Grant 4096. |
| |
Keywords: | Probabilistic analysis of algorithms Grouping by swapping Memory compaction Exponential of a matrix |
本文献已被 SpringerLink 等数据库收录! |
|