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

28
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
24
25
26
27
28
29
30
31
1
2021 Július

Kiemelt híreink

Nagy Gábor, Rácz Szilárd és Jóna László tanulmányai a Magyar Urbanisztikai Társaság kötetében

Nagy Gábor, Rácz Szilárd és Jóna László tanulmányai a Magyar Urbanisztikai Társaság kötetében Városok - Tervezés - Ingatlanpiac: Az urbanisztika aktuális kérdései. Szerkesztette: Salamin Géza - Tóth Bálint. Budapest, 2021.

Sikeresebbek leszünk az olimpián, ha több pénzt és energiát áldozunk a sportra? - Csurilla Gergely és Fertő Imre válaszol a KRTK blogban

Sikeresebbek leszünk az olimpián, ha több pénzt és energiát áldozunk a sportra? -  Csurilla Gergely és Fertő Imre válaszol a KRTK blogban Az olimpiai játékok előtt mindig megindul a találgatás, hogy hány olimpiai arany, ezüst vagy bronzéremre van esélyünk. A közvélemény egy része úgy véli, hogy ilyenkor nemcsak a sportolók, hanem a sportirányítás, és tágabb értelemben az aktuális kormányzat sportpolitikája is vizsgázik. Ezek a megfontolások nem teljesen megalapozatlanok. Az elmúlt évtizedekben számos, korábban sikeres ország más okból döntött úgy, hogy hatalmas erőforrásokat fordít az olimpiai sikerek növelésére. Ausztrália például az 1976-os montreali és a 2000-es sydneyi olimpia között 5 éremről 60 éremre növelte teljesítményét. Az Egyesült Királyság, amely napjainkban a világ egyik legsikeresebb sportirányítási rendszerével rendelkezik, a 2016-os riói nyári olimpiai játékok éremtáblázatán az Egyesült Államok után a második helyen végzett – többek között az 1997-ben bevezetett új sportirányítási rendszernek és az azóta soha nem látott mértékben megnövelt finanszírozásnak köszönhetően.

Pályázati felhívás intézetigazgató munkakör betöltésére a KRTK Regionális Kutatások Intézetében

Pályázati felhívás intézetigazgató munkakör betöltésére a KRTK Regionális Kutatások Intézetében A Közgazdaság- és Regionális Tudományi Kutatóközpont pályázatot hirdet intézetigazgató munkakör betöltésére a KRTK Regionális Kutatások Intézetében. A pályázat benyújtásának határideje: 2021. szeptember 15. Az intézetigazgató jogállása: a tevékenységét munkaviszony keretében, kutatói munkakörhöz tartozó feladatok mellett látja el. Az intézetigazgató felett a munkáltatói jogok gyakorlása a Kutatóközpont főigazgatójának hatáskörébe tartozik. Az intézetigazgató munkaköre határozott időre, legfeljebb 3 évig terjedő időtartamra szól.

További híreink »