Width-based search is an effective approach to classical planning which has produced many successful algorithms over the years. A key feature which distinguishes width-based search from classic heuristic search algorithms is the use of specific structural properties of the explored state space to guide the exploration and goal-directed heuristic measures for exploitation. The structural properties are captured as an n-ary relation over the fluents which is processed to compute the state novelty. The size of the relation and the time complexity of computing novelty measure is exponential on the arity n. Approximate novelty search introduces novel polynomial approximations of state novelty and width-based search. It uses Bloom filter to efficiently represent the interpretation of the relational predicate and random sampling in the computation of state novelty. It also uses an adaptive policy which decides to delay the generation of successor states. In this paper, we explain the integration of these two techniques into the polynomial-time variant of Best-First Width Search (BFWS), one of the most successful width-based algorithm in satisficing planning.