3 papers
cs.GT2026
Computational Social Choice: Research & Development
Dorothea Baumeister, Ratip Emin Berker, Niclas Boehmer +7
Computational social choice (COMSOC) studies principled ways to aggregate conflicting individual preferences into collective decisions. In this paper, we call for an increased effo…
cs.GT2025
Allocation of Indivisible Items with a Common Preference Graph: Minimizing Total Dissatisfaction
Nina Chiarelli, Clément Dallard, Andreas Darmann +4
Allocating indivisible items among a set of agents is a frequently studied discrete optimization problem. In the setting considered in this work, the agents' preferences over the i…
cs.CC2024
An even simpler hard variant of Not-All-Equal 3-SAT
Andreas Darmann, Janosch Döcker, Britta Dorn
We show that Not-All-Equal 3-Sat remains NP-complete when restricted to instances that simultaneously satisfy the following properties: (i) The clauses are given as the disjoint un…