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 Tools annual

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 Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We study four NP-hard optimal seat arrangement problems [Bodlaender et al.,2020a], which each have as input a set of n agents, where each agent hascardinal preferences over other agents, and an n-vertex undirected graph(called seat graph). The task is to assign each agent to a distinct vertex inthe seat graph such that either the sum of utilities or the minimum utility ismaximized, or it is envy-free or exchange-stable. Aiming at identifying hardand easy cases, we extensively study the algorithmic complexity of the fourproblems by looking into natural graph classes for the seat graph (e.g., paths,cycles, stars, or matchings), problem-specific parameters (e.g., the number ofnon-isolated vertices in the seat graph or the maximum number of agents towardswhom an agent has non-zero preferences), and preference structures (e.g.,non-negative or symmetric preferences). For strict preferences and seat graphswith disjoint edges and isolated vertices, we correct an error by Bodlaender etal. [2020b] and show that finding an envy-free arrangement remains NP-hard inthis case.

Optimal Seat Arrangement: What Are the Hard and Easy Cases?