August 21, 2025

Non-Submodular Maximization Subject to a Knapsack Constraint on the Integer Lattice

Puntos clave

The proposed algorithm achieves a provable approximation ratio under defined conditions, enhancing optimization efforts.
Experimental results support the efficiency of maximizing non-submodular objectives in real-world settings for various applications.
This work outlines the first significant approximation guarantee for non-submodular maximization problems in the integer lattice context.
The algorithm builds on existing knowledge of submodular functions while addressing their non-submodular counterparts effectively.

Resumen

The emergence of applications in machine learning, social networks, and sensor placement has naturally introduced challenges in maximizing submodular or non-submodular functions over integer lattices under knapsack constraints. While efficient algorithms exist for maximizing monotone non-negative submodular functions over both finite sets and integer lattices, these methods do not generalize straightforwardly to non-submodular objectives. To address this gap, we propose a two-phase greedy algorithm with a provable approximation ratio of Formula: see text, given that the objective function satisfies the Diminishing Return ratio (DR-ratio) Formula: see text and the generalized curvature Formula: see text. To our knowledge, this represents the first non-trivial approximation guarantee for such problem. Experimental evaluations demonstrate the algorithm’s practical effectiveness.

Me gusta

Guardar