1621. Minimizing Dissatisfaction of an Allocation on a Common Preference Graph
Invited abstract in session MD-20: Problems on graphs, stream Combinatorial Optimization.
Monday, 14:30-16:00Room: Esther Simpson 2.11
Authors (first author is the speaker)
| 1. | Ulrich Pferschy
|
| Department of Operations and Information Systems, University of Graz | |
| 2. | Nina Chiarelli
|
| FAMNIT, University of Primorska | |
| 3. | Clément Dallard
|
| Université d’Orléans | |
| 4. | Andreas Darmann
|
| Department of Operations and Information Systems, University of Graz | |
| 5. | Stefan Lendl
|
| Institute of Operations und Information Systems, University of Graz | |
| 6. | Martin Milanic
|
| UP IAM and UP FAMNIT, University of Primorska | |
| 7. | Peter Mursic
|
| FAMNIT, University of Primorska |
Abstract
We consider the allocation of indivisible items to agents, when all agents’ preferences are expressed by a common directed acyclic graph. The vertices of the graph represent items and an arc (a,b) means that item a is preferred over item b. The dissatisfaction of an agent is measured by the number of non-assigned items which are desired by the agent and for which no more preferred item is given to the agent.
We pursue two different goals of an allocation, either efficiency (measured by the total dissatisfaction over all agents) or fairness (given by the maximum dissatisfaction among agents).
For both problems we study the status of computational complexity and obtain NP-hardness results as well as polynomial time algorithms with respect to different underlying graph structures. Focusing on the number of agents, the problem is rather easy for 2 agents, but becomes NP-hard for at least 3 agents, even on fairly restricted graphs. However, depending on the objective function, we obtain polynomial time algorithms for special graph classes, such as out-stars, out-trees and polytrees. Furthermore, we consider graphs of treewidth two and exploit modular graph decompositions to obtain fixed parameter tractability results.
Keywords
- Combinatorial Optimization
- Algorithms
- Graphs and Networks
Status: accepted
Back to the list of papers