Optimal Seat Arrangement: What Are the Hard and Easy Cases?
Authors: Esra Ceylan, Jiehua Chen, Sanjukta Roy
IJCAI 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study four NP-hard optimal seat arrangement problems, which each have as input a set of n agents, where each agent has cardinal preferences over other agents, and an n-vertex undirected graph (called seat graph). The task is to assign each agent to a distinct vertex in the seat graph such that either the sum of utilities or the minimum utility is maximized, or it is envy-free or exchange-stable. Aiming at identifying hard and easy cases, we extensively study the algorithmic complexity of the four problems by looking into natural graph classes for the seat graph (e.g., paths, cycles, stars, or matchings), problem-specific parameters (e.g., the number of non-isolated vertices in the seat graph or the maximum number of agents towards whom an agent has non-zero preferences), and preference structures (e.g., non-negative or symmetric preferences). |
| Researcher Affiliation | Academia | Esra Ceylan1 , Jiehua Chen1 and Sanjukta Roy2 1TU Wien, Austria 2 Pennsylvania State University |
| Pseudocode | No | The paper discusses theoretical proofs and algorithmic complexity but does not provide structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not mention providing open-source code for the described methodology. |
| Open Datasets | No | This paper is theoretical and does not use or reference any datasets for training. |
| Dataset Splits | No | This paper is theoretical and does not involve dataset splits for validation. |
| Hardware Specification | No | The paper is theoretical and does not describe experimental hardware specifications. |
| Software Dependencies | No | The paper is theoretical and does not mention specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup or hyperparameters. |