Contiguous Allocation of Binary Valued Indivisible Items on a Path

We study the problem of allocating indivisible binary-valued items on a path among agents. The objective is to find a fair and efficient allocation in which each agent's bundle forms a contiguous block on the path. We demonstrate that deciding whether every item can be allocated to an agent who wants it is NP-complete. Consequently, we provide fixed-parameter tractable (FPT) algorithms for maximizing utilitarian social welfare, with respect to the optimum value and the number of agents. Additionally, we present a 2-approximation algorithm for the special case when the maximum utility is equal to the number of items. Furthermore, we establish that deciding whether the maximum egalitarian social welfare is at least 2 or at most 1 is an NP-complete problem. We also explore the case where the order of the blocks of items allocated to the agents is predetermined. In this case, we show that both maximum utilitarian social welfare and egalitarian social welfare can be computed in polynomial time. However, we determine that checking the existence of an EF1 allocation is NP-complete.