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 problem of efficiently and fairly allocating a set ofindivisible goods among agents with identical and additive valuations for thegoods. The objective is to maximize the Nash social welfare, which is thegeometric mean of the agents' valuations. While maximizing the Nash socialwelfare is NP-hard, a PTAS for this problem is presented by Nguyen and Rothe.The main contribution of this paper is to design a first additive PTAS for thisproblem, that is, we give a polynomial-time algorithm that maximizes the Nashsocial welfare within an additive error $\varepsilon v_{\rm max}$, where$\varepsilon$ is an arbitrary positive number and $v_{\rm max}$ is the maximumutility of a good. The approximation performance of our algorithm is betterthan that of a PTAS. The idea of our algorithm is simple; we apply apreprocessing and then utilize an additive PTAS for the target load balancingproblem given recently by Buchem et al. However, a nontrivial amount of work isrequired to evaluate the additive error of the output.

An Additive Approximation Scheme for the Nash Social Welfare Maximization with Identical Additive Valuations