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

We present a new type of monotone submodular functions: \emph{multi-peaksubmodular functions}. Roughly speaking, given a family of sets $\cF$, weconstruct a monotone submodular function $f$ with a high value $f(S)$ for everyset $S \in {\cF}$ (a "peak"), and a low value on every set that does notintersect significantly any set in $\cF$.  We use this construction to show that a better than$(1-\frac{1}{2e})$-approximation ($\simeq 0.816$) for welfare maximization incombinatorial auctions with submodular valuations is (1) impossible in thecommunication model, (2) NP-hard in the computational model where valuationsare given explicitly. Establishing a constant approximation hardness for thisproblem in the communication model was a long-standing open question. Thevaluations we construct for the hardness result in the computational modeldepend only on a constant number of items, and hence the result holds even ifthe players can answer arbitrary queries about their valuation, includingdemand queries.  We also study two other related problems that received some attentionrecently: max-min allocation (for which we also get hardness of $(1-\frac 1{2e}+\epsilon)$-approximation, in both models), and combinatorial publicprojects (for which we prove hardness of $(3/4+\epsilon)$-approximation in thecommunication model, and hardness of $(1 -\frac 1 e+\epsilon)$-approximation inthe computational model, using constant size valuations).

On the Hardness of Welfare Maximization in Combinatorial Auctions with Submodular Valuations