2 papers
cs.DS2026
Linear-Query Deterministic Approximation for Non-monotone Submodular Maximization under a Knapsack Constraint
Zihui Liu, Zhijie Zhang
Submodular maximization under a knapsack constraint (SMK) is a fundamental combinatorial optimization problem with broad applications across machine learning and data mining. Motiv…
cs.DS2026
Budget-Independent Influence Maximization in Nearly Linear Time
Zhijie Zhang
Influence maximization asks for seed vertices that maximize the expected spread of a diffusion process in a network. Standard near-optimal-time algorithms based on reverse-reac…