Schlotter Ildikó szerzőtársakkal írt tudományos cikke megjelent az Algorithmica szakfolyóiratban

2021.04.07 | 10:07
Schlotter Ildikó szerzőtársakkal írt tudományos cikke megjelent az Algorithmica szakfolyóiratban

Published: 26 March 2021

Obtaining a Proportional Allocation by Deleting Items

Britta Dorn - Ronald de Haan - Ildikó Schlotter

Abstract

We consider the following control problem on fair allocation of indivisible goods. Given a set I of items and a set of agents, each having strict linear preferences over the items, we ask for a minimum subset of the items whose deletion guarantees the existence of a proportional allocation in the remaining instance; we call this problem Proportionality by Item Deletion (PID). Our main result is a polynomial-time algorithm that solves PID for three agents. By contrast, we prove that PID is computationally intractable when the number of agents is unbounded, even if the number k of item deletions allowed is small—we show that the problem is W[3] -hard with respect to the parameter k. Additionally, we provide some tight lower and upper bounds on the complexity of PID when regarded as a function of |I| and k. Considering the possibilities for approximation, we prove a strong inapproximability result for PID. Finally, we also study a variant of the problem where we are given an allocation π in advance as part of the input.

« Vissza a listához

Eseménynaptár

H

K

Sz

Cs

P

Szo

V

29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
2
2021 Április

Kiemelt híreink

Járványszerűen terjed a koronavírus a tudományos életben - Orosz Ágnes írása a KRTK blogban

Járványszerűen terjed a koronavírus a tudományos életben - Orosz Ágnes írása a KRTK blogban Számszerű elemzés nélkül is kijelenthető, hogy a koronavírus témaköre uralja a hazai és nemzetközi médiát már több, mint egy éve. Az internetes tartalmak és persze a nyomtatott sajtó esetében is elképzelhetetlen, hogy úgy teljen el egy nap, hogy valamilyen kontextusban ne találkozzunk a kifejezéssel. A vírus magyarországi megjelenésekor, 2020 március elején már 6100 hír született koronavírus témában naponta a különböző magyar híroldalakon, és azóta is rendre a vezető hírek között találjuk a COVID-19 tartalmakat. Ez a tudományos kutatás esetében sincs másképp.

Schlotter Ildikó szerzőtársakkal írt tudományos cikke megjelent az Algorithmica szakfolyóiratban

Schlotter Ildikó szerzőtársakkal írt tudományos cikke megjelent az Algorithmica szakfolyóiratban Published: 26 March 2021

Braun Erik, Iloskics Zita és szerzőtársaik cikke a Regional Statistics friss számában

Braun Erik, Iloskics Zita és szerzőtársaik cikke a Regional Statistics friss számában Regional Statistics, Vol. 11. No. 2. 2021 - A KSH Területi Statisztika c. folyóiratának negyedévente megjelenő angol nyelvű változata

További híreink »