Fast Pareto Optimization Using Sliding Window Selection
Pareto optimization using evolutionary multi-objective algorithms has been widely applied to solve constrained submodular optimization problems. A crucial factor determining the runtime of the used evolutionary algorithms to obtain good approximations is the population size of the algorithms which grows with the number of trade-offs that the algorithms encounter. In this paper, we introduce a sliding window speed up technique for recently introduced algorithms. We prove that our technique eliminates the population size as a crucial factor negatively impacting the runtime and achieves the same theoretical performance guarantees as previous approaches within less computation time. Our experimental investigations for the classical maximum coverage problem confirms that our sliding window technique clearly leads to better results for a wide range of instances and constraint settings.
Code (0)
등록된 구현이 없습니다.
Tasks
Evolutionary AlgorithmsMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Sliding Window 3-Objective Pareto Optimization for Problems with Chance Constraints
Constrained single-objective problems have been frequently tackled by evolutionary multi-objective algorithms where the constraint is relaxed into an additional objective. Recently, it has been shown that Pareto optimiza…
Fast Automatic Feature Selection for Multi-Period Sliding Window Aggregate in Time Series
As one of the most well-known artificial feature sampler, the sliding window is widely used in scenarios where spatial and temporal information exists, such as computer vision, natural language process, data stream, and …
feature selectionTime SeriesTime Series AnalysisNLL-Guided Full-Attention Layer Selection for Training-Free Sliding-Window Adaptation
Hybrid attention models that mix full and sliding-window attention across layers offer a promising approach to efficient long-context inference, but the critical question of \emph{which layers} should retain full attenti…
Efficient Representative Subset Selection over Sliding Windows
Representative subset selection (RSS) is an important tool for users to draw insights from massive datasets. Existing literature models RSS as the submodular maximization problem to capture the "diminishing returns" prop…
Fast Video Generation with Sliding Tile Attention
Diffusion Transformers (DiTs) with 3D full attention power state-of-the-art video generation, but suffer from prohibitive compute cost -- when generating just a 5-second 720P video, attention alone takes 800 out of 945 s…
Video Generation