EUVIMEDEUVIMED entdecken
Crossref

Approximating Proportional and Maximin Allocations on D-Claw-Free Graphs

Zbigniew Lonc

Journal of Artificial Intelligence Research · 28.02.2026 · 85

DOI: 10.1613/jair.1.17263 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of Artificial Intelligence Research, online erschienen am 28.02.2026. Verfasst von Zbigniew Lonc.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We study the problem of fair allocation of indivisible goods that form a graph and the bundles that are distributed to agents are connected subgraphs of this graph. We focus on the proportional and the maximin share fairness criteria. It is well-known that allocations satisfying these criteria may not exist for many graphs including complete graphs and cycles. Therefore, it is natural to look for approximate allocations, i.e., allocations guaranteeing each agent a certain portion of the value that is satisfactory to her. In this paper we consider the class of graphs of goods which do not contain a star with d+1 edges (where d > 1) as an induced subgraph. This is a large class of graphs containing graphs with the maximum degree bounded by d. For this class of graphs we show a theorem which specifies what fraction of the proportional share can be guaranteed to each of n agents if the values of single goods for the agents are bounded by a given fraction of this share. Furthermore, an allocation ensuring such a guarantee can be computed in polynomial time. This theorem can be viewed as analogous to a result by Hill in1987, who solved a similar problem for proportional allocations without connectivity constraints. Moreover, for the same class of graphs of goods, we prove that there is an allocation assigning each of n agents a connected bundle of value at least n/(d(n-1)+1) > 1/d of her maximin share, and this allocation can be computed in polynomial time.

Zitieren

APA

Lonc, Z. (2026). Approximating Proportional and Maximin Allocations on D-Claw-Free Graphs. Journal of Artificial Intelligence Research, 85. https://doi.org/10.1613/jair.1.17263

Vancouver

Lonc Z. Approximating Proportional and Maximin Allocations on D-Claw-Free Graphs. Journal of Artificial Intelligence Research. 2026;85. doi:10.1613/jair.1.17263

BibTeX
@article{Lonc2026,
  author = {Lonc, Zbigniew},
  title = {Approximating Proportional and Maximin Allocations on D-Claw-Free Graphs},
  journal = {Journal of Artificial Intelligence Research},
  year = {2026},
  volume = {85},
  doi = {10.1613/jair.1.17263}
}
Kostenlos starten →