English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

We study the online submodular maximization problem with free disposal undera matroid constraint. Elements from some ground set arrive one by one inrounds, and the algorithm maintains a feasible set that is independent in theunderlying matroid. In each round when a new element arrives, the algorithm mayaccept the new element into its feasible set and possibly remove elements fromit, provided that the resulting set is still independent. The goal is tomaximize the value of the final feasible set under some monotone submodularfunction, to which the algorithm has oracle access.  For $k$-uniform matroids, we give a deterministic algorithm with competitiveratio at least $0.2959$, and the ratio approaches $\frac{1}{\alpha_\infty}\approx 0.3178$ as $k$ approaches infinity, improving the previous best ratioof $0.25$ by Chakrabarti and Kale (IPCO 2014), Buchbinder et al. (SODA 2015)and Chekuri et al. (ICALP 2015). We also show that our algorithm is optimalamong a class of deterministic monotone algorithms that accept a new arrivingelement only if the objective is strictly increased.  Further, we prove that no deterministic monotone algorithm can be strictlybetter than $0.25$-competitive even for partition matroids, the most modestgeneralization of $k$-uniform matroids, matching the competitive ratio byChakrabarti and Kale (IPCO 2014) and Chekuri et al. (ICALP 2015).Interestingly, we show that randomized algorithms are strictly more powerful bygiving a (non-monotone) randomized algorithm for partition matroids with ratio$\frac{1}{\alpha_\infty} \approx 0.3178$.

Online Submodular Maximization with Free Disposal: Randomization Beats 0.25 for Partition Matroids