תוקף עדפיות-עמידות-עדרי-פואסון למקסימיזציה של תת-מודולריות על מטרידים

תקציר מקורי באנגליתarXiv:2608.12134v2 Announce Type: replace Abstract: We study nonnegative submodular maximization on $n$ elements subject to a general matroid of rank $k$, when the offline algorithm is given an arbitrary controlled value oracle. Our main result is an adversarial resilience theorem for the Spiteful Greedy Swap Poisson Process (SGS-Poisson): without modifying its Poisson intensity, single-element exchange rule, or spiteful drop step, the algorithm retains limiting approximation factors $1/e$ for non-monotone objectives and $1-1/e$ for monotone objectives. More precisely, given an error bound $\xi\ge0$, under every controlled oracle $\widehat f$ satisfying $|\widehat f(S)-f(S)|\le \xi$ for every set $S$, our implementation returns a feasible set with expected value at least $(1/e-\varepsilon)