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

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

Kiemelt híreink

New journal article by Anikó Bíró, researcher of KTI in Agricultural Economics

New journal article by Anikó Bíró, researcher of KTI in Agricultural Economics First published: 11 June 2021

Mennyire fájna a költségvetésnek, ha szabadabban dönthetnénk a nyugdíjba vonulásról? - Simonovits András cikke a KRTK Blogban

Mennyire fájna a költségvetésnek, ha szabadabban dönthetnénk a nyugdíjba vonulásról? - Simonovits András cikke a KRTK Blogban Rugalmas nyugdíjkorhatárról akkor beszélünk, ha néhány évvel az általános nyugdíjkorhatár elérése előtt és után is nyugdíjba lehet vonulni, csak a havi nyugdíj úgy csökken vagy növekszik, hogy az életpálya-befizetések és -kifizetések egyenlege fennmarad. 2009-ig a levonás túl kevés volt, 2011-2012-ben pedig – a Nők40 kivételével – megszűnt az előrehozott nyugdíj. Korábban számos cikkben érveltem a rugalmas nyugdíjkorhatár bevezetése mellett, de másokat követve, megelégedtem a statikus (pontosabban: állandósult állapotbeli elemzéssel). Most dinamikus kiterjesztéssel pótolom a hiányt.

Hardi Tamás és Ocskay Gyula tanulmánya megjelent a Földrajzi Közlemények idei második negyedéves számában

Hardi Tamás és Ocskay Gyula tanulmánya megjelent a Földrajzi Közlemények idei második negyedéves számában A Magyar Földrajzi Társaság tudományos folyóirata. Évf. 145, szám 2 (2021) - megjelent: 2021-05-26

További híreink »