NDLI: On the Probable Performance of Heuristics for Bandwidth Minimization

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Turner, Jonathan S.
Copyright Year	1986
Abstract	Most research in algorithm design relies on worst-case analysis for performance comparisons. Unfortunately, worst-case analysis does not always provide an adequate measure of an algorithms effectiveness. This is particularly true in the case of heuristic algorithms for hard combinatorial problems. In such cases, analysis of the probable performance can yield more meaningful results and can provide insight leading to better algorithms. The problem of minimizing the bandwidth of a sparse symmetric matrix by performing simultaneous row and column permutations, is an example of a problem for which there are well-known heuristics whose practical success has lacked a convincing analytical explanation. A class of heuristics introduced by Cuthill and McKee in 1969, and referred to here as the level algorithms, are the basis for bandwidth minimization routines that have been widely used for over a decade. At the same time, it is easy to construct examples, showing that the level algorithms can produce solutions that differ from optimal by an arbitrarily large factor. This paper provides an analytical explanation for the practical success of the level algorithms, by showing that for random matrices having optimal bandwidth no larger than k, any level algorithm will produce solutions that differ from optimal by a small constant factor. The analysis also suggests another class of algorithms with better performance. One algorithm in this class is shown to produce solutions that are nearly optimal.
Starting Page	561
Ending Page	580
Page Count	20
File Format	PDF
ISSN	00975397
DOI	10.1137/0215041
e-ISSN	10957111
Journal	SIAM Journal on Computing (SMJCAT)
Issue Number	2
Volume Number	15
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2006-07-13
Access Restriction	Subscribed
Subject Keyword	bandwidth minimization problem heuristic algorithms NP-completeness probabilistic analysis approximation algorithms probable performance
Content Type	Text
Resource Type	Article
Subject	Mathematics Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

The Probabilistic Analysis of a Heuristic for the Assignment Problem

On Some Variants of the Bandwidth Minimization Problem

On The Probable Performance Of Heuristics For Bandwidth Minimization (1986)

Web of lossy adapters for interface interoperability: An algorithm and NP-completeness of minimization

Approximation algorithms for the bandwidth minimization problem for caterpillar graphs

Approximation of the Consecutive Ones Matrix Augmentation Problem

The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete

Gadgets, Approximation, and Linear Programming

Average Performance of Heuristics for Satisfiability

On the Probable Performance of Heuristics for Bandwidth Minimization

Similar Documents

The Probabilistic Analysis of a Heuristic for the Assignment Problem

On Some Variants of the Bandwidth Minimization Problem

On The Probable Performance Of Heuristics For Bandwidth Minimization (1986)

Web of lossy adapters for interface interoperability: An algorithm and NP-completeness of minimization

Approximation algorithms for the bandwidth minimization problem for caterpillar graphs

Approximation of the Consecutive Ones Matrix Augmentation Problem

The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete

Gadgets, Approximation, and Linear Programming

Average Performance of Heuristics for Satisfiability

On the Probable Performance of Heuristics for Bandwidth Minimization