  The next release problem (NRP) aims to effectively select software
requirements in order to acquire maximum customer profits. As an NP-hard
problem in software requirement engineering, NRP lacks efficient approximate
algorithms for large scale instances. The backbone is a new tool for tackling
large scale NP-hard problems in recent years. In this paper, we employ the
backbone to design high performance approximate algorithms for large scale NRP
instances. Firstly we show that it is NP-hard to obtain the backbone of NRP.
Then, we illustrate by fitness landscape analysis that the backbone can be well
approximated by the shared common parts of local optimal solutions. Therefore,
we propose an approximate backbone based multilevel algorithm (ABMA) to solve
large scale NRP instances. This algorithm iteratively explores the search
spaces by multilevel reductions and refinements. Experimental results
demonstrate that ABMA outperforms existing algorithms on large instances in
terms of solution quality and running time.
