3 papers
cs.DS2026
If it is Good Then Drop it -- a Spiteful Poisson Process for Submodular Maximization
Ariel Kulik, Thiago Oliveira, Roy Schwartz +1
We study the problem of maximizing a general and not necessarily monotone submodular function subject to a matroid independence constraint. This problem has a rich history, with mu…
cs.DS2026
Tight Algorithm and Hardness for Submodular Linear Ordering
Evan Abboud, Roy Schwartz
We consider the Minimum Linear Ordering Problem: given a ground set of cardinality and a non-negative set function , the goal is…
cs.DS2026
A Poisson Process for Submodular Maximization
Amit Ganz Rozenman, Ariel Kulik, Roy Schwartz +1
We study the problem of maximizing a monotone submodular function subject to a matroid independence constraint. For more than a decade, a rich body of work has studied this problem…