The open archive for STFC research publications

Full Record Details

DOI 10.5286/raltr.2011019
Persistent URL http://purl.org/net/epubs/work/61232
Record Status Checked
Record Id 61232
Title Level-based heuristics and hill climbing for the antibandwidth maximization problem
Abstract The antibandwidth maximization problem is the dual of the well-known bandwidth minimization problem. In this paper, we consider the feasibility of adapting heuristic algorithms for the bandwidth minimization problem to the antibandwidth maximization problem. In particular, using an inexpensive level-based heuristic we obtain an initial ordering that we re ne using a hill-climbing algorithm. This approach performs well on matrices coming from a range of practical problems with an underlying mesh. Comparisons with existing approaches show that, on this class of problems, our algorithm can be competitive with recently reported results in terms of quality while being signi cantly faster and applicable to much larger problems.
Organisation CSE , CSE-NAG , STFC
Keywords antibandwidth maximization , sparse matrices
Funding Information
Related Research Object(s): 11353379
Licence Information:
Language English (EN)
Type Details URI(s) Local file(s) Year
Report RAL Technical Reports RAL-TR-2011-019. 2011. RAL-TR-2011-019.pdf 2011