Paper Info
Title
Probabilistic Analysis of a Grouping Algorithm
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→∞ or asn/m→0.
Year
DOI
Venue
1991
10.1007/BF01759041
Algorithmica
Keywords
Field
DocType
probabilistic analysis of algorithms,memory compaction,grouping by swapping,exponential of a matrix.
Memory compaction,Discrete mathematics,Swap (computer programming),Combinatorics,Algorithm,Probabilistic analysis of algorithms,Sorting,Autonomous system (Internet),Asymptotically optimal algorithm,Matrix exponential,Mathematics
Journal
Volume
Issue
ISSN
6
2
0178-4617
Citations 
PageRank 
References 
0
0.34
0
Authors
2
Name
Order
Citations
PageRank
Martin D. F. Wong13525363.70
Edward M. Reingold22214563.65