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/

Global: Zendy Plus annual

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

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The problem of non-monotone $k$-submodular maximization under a knapsackconstraint ($\kSMK$) over the ground set size $n$ has been raised in manyapplications in machine learning, such as data summarization, informationpropagation, etc. However, existing algorithms for the problem are facingquestioning of how to overcome the non-monotone case and how to fast return agood solution in case of the big size of data. This paper introduces twodeterministic approximation algorithms for the problem that competitivelyimprove the query complexity of existing algorithms.  Our first algorithm, $\LAA$, returns an approximation ratio of $1/19$ within$O(nk)$ query complexity. The second one, $\RLA$, improves the approximationratio to $1/5-\epsilon$ in $O(nk)$ queries, where $\epsilon$ is an inputparameter.  Our algorithms are the first ones that provide constant approximation ratioswithin only $O(nk)$ query complexity for the non-monotone objective. They,therefore, need fewer the number of queries than state-of-the-the-art ones by afactor of $\Omega(\log n)$.  Besides the theoretical analysis, we have evaluated our proposed ones withseveral experiments in some instances: Influence Maximization and SensorPlacement for the problem. The results confirm that our algorithms ensuretheoretical quality as the cutting-edge techniques and significantly reduce thenumber of queries.

Robust Approximation Algorithms for Non-monotone $k$-Submodular Maximization under a Knapsack Constraint