Introduce lazy greedy algorithm to _solve_hssp
#5285
Labels
code-fix
Change that does not change the behavior, such as code refactoring.
enhancement
Change that does not break compatibility and not affect public interfaces, but improves performance.
needs-discussion
Issue/PR which needs discussion.
Motivation
Practically speed-up
_solve_hssp()
using lazy greedy algorithm.Description
The current implementation of$1-1/e$ (refer to https://doi.org/10.1007/BFb0121195) for monotone cases and obtains practically good solution for non-monotone cases.
_solve_hssp()
relies on the greedy algorithm for submodular maximization problems with a cardinality constraint. the greedy algorithm guarantees the best approximation ratio ofTo further enhance performance, I propose introducing the lazy greedy algorithm (see https://doi.org/10.1007/BFb0006528) to the hypervolume subset selection problems. This extension allows the algorithm to strategically delay oracle calls until necessary, leveraging the submodular property for practical speed improvements over the naive greedy algorithm. Notably, the number of oracle calls is maintained at most equivalent to the original greedy algorithm.
This straightforward combination of contribution calculation and lazy strategy has been experimentally validated in https://doi.org/10.1109/CEC48606.2020.9185878.
Alternatives (optional)
We need to examine benchmark results to judge whether the lazy strategy really accelerates
_solve_hssp()
. This is because lazy greedy has the overhead of heap operations and can be slow depending on the input.Additional context (optional)
No response
The text was updated successfully, but these errors were encountered: