Probabilistic analysis of a grouping algorithm

D. F. Wong; Edward M. Reingold

doi:10.1007/BF01759041

Probabilistic analysis of a grouping algorithm

D. F. Wong^*, Edward M. Reingold

^*Corresponding author for this work

Office of the Provost

Research output: Contribution to journal › Journal article › peer-review

2 Citations (Scopus)

Abstract

We study the grouping by swapping problem, which occurs in memory compaction and in computing the exponential of a matrix. In this problem we are given a sequence of n 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 called MEDIAN that works by sorting the numbers in the sequence according to their median positions. Our results show that the expected behavior of MEDIAN is within 10% of optimal and is asymptotically optimal as n/m→∞ or as n/m→0.

Original language	English
Pages (from-to)	192-206
Number of pages	15
Journal	Algorithmica
Volume	6
Issue number	1-6
DOIs	https://doi.org/10.1007/BF01759041
Publication status	Published - Jun 1991

Scopus Subject Areas

General Computer Science
Computer Science Applications
Applied Mathematics

User-Defined Keywords

Exponential of a matrix
Grouping by swapping
Memory compaction
Probabilistic analysis of algorithms

Access to Document

10.1007/BF01759041

Cite this

@article{e0d4f30f22ca4643ac6dd8f21f777c24,

title = "Probabilistic analysis of a grouping algorithm",

abstract = "We study the grouping by swapping problem, which occurs in memory compaction and in computing the exponential of a matrix. In this problem we are given a sequence of n 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 called MEDIAN that works by sorting the numbers in the sequence according to their median positions. Our results show that the expected behavior of MEDIAN is within 10% of optimal and is asymptotically optimal as n/m→∞ or as n/m→0.",

keywords = "Exponential of a matrix, Grouping by swapping, Memory compaction, Probabilistic analysis of algorithms",

author = "Wong, {D. F.} and Reingold, {Edward M.}",

year = "1991",

month = jun,

doi = "10.1007/BF01759041",

language = "English",

volume = "6",

pages = "192--206",

journal = "Algorithmica",

issn = "0178-4617",

publisher = "Springer New York",

number = "1-6",

}

TY - JOUR

T1 - Probabilistic analysis of a grouping algorithm

AU - Wong, D. F.

AU - Reingold, Edward M.

PY - 1991/6

Y1 - 1991/6

N2 - We study the grouping by swapping problem, which occurs in memory compaction and in computing the exponential of a matrix. In this problem we are given a sequence of n 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 called MEDIAN that works by sorting the numbers in the sequence according to their median positions. Our results show that the expected behavior of MEDIAN is within 10% of optimal and is asymptotically optimal as n/m→∞ or as n/m→0.

AB - We study the grouping by swapping problem, which occurs in memory compaction and in computing the exponential of a matrix. In this problem we are given a sequence of n 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 called MEDIAN that works by sorting the numbers in the sequence according to their median positions. Our results show that the expected behavior of MEDIAN is within 10% of optimal and is asymptotically optimal as n/m→∞ or as n/m→0.

KW - Exponential of a matrix

KW - Grouping by swapping

KW - Memory compaction

KW - Probabilistic analysis of algorithms

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

U2 - 10.1007/BF01759041

DO - 10.1007/BF01759041

M3 - Journal article

AN - SCOPUS:52449145722

SN - 0178-4617

VL - 6

SP - 192

EP - 206

JO - Algorithmica

JF - Algorithmica

IS - 1-6

ER -

Probabilistic analysis of a grouping algorithm

Abstract

Scopus Subject Areas

User-Defined Keywords

Access to Document

Other files and links

Fingerprint

Cite this