2 Search Results for "Hummel, Britta"

Document

DOI: 10.4230/LIPIcs.ISAAC.2025.54

Reforming an Unfair Allocation by Exchanging Goods

Authors: Sheung Man Yuen, Ayumi Igarashi, Naoyuki Kamiyama, and Warut Suksompong

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract

Fairly allocating indivisible goods is a frequently occurring task in everyday life. Given an initial allocation of the goods, we consider the problem of reforming it via a sequence of exchanges to attain fairness in the form of envy-freeness up to one good (EF1). We present a vast array of results on the complexity of determining whether it is possible to reach an EF1 allocation from the initial allocation and, if so, the minimum number of exchanges required. In particular, we uncover several distinctions based on the number of agents involved and their utility functions. Furthermore, we derive essentially tight bounds on the worst-case number of exchanges needed to achieve EF1.

Cite as

Sheung Man Yuen, Ayumi Igarashi, Naoyuki Kamiyama, and Warut Suksompong. Reforming an Unfair Allocation by Exchanging Goods. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 54:1-54:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{yuen_et_al:LIPIcs.ISAAC.2025.54,
  author =	{Yuen, Sheung Man and Igarashi, Ayumi and Kamiyama, Naoyuki and Suksompong, Warut},
  title =	{{Reforming an Unfair Allocation by Exchanging Goods}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{54:1--54:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.54},
  URN =		{urn:nbn:de:0030-drops-249626},
  doi =		{10.4230/LIPIcs.ISAAC.2025.54},
  annote =	{Keywords: fair division, indivisible goods, envy-freeness, exchanges}
}

Document

DOI: 10.4230/DagSemProc.08091.14

Scene Understanding of Urban Road Intersections with Description Logic

Authors: Britta Hummel, Werner Thiemann, and Irina Lulcheva

Published in: Dagstuhl Seminar Proceedings, Volume 8091, Logic and Probability for Scene Interpretation (2008)

Abstract

Road recognition from video sequences has been solved robustly only for small, often simplified subsets of possible road configurations. A massive augmentation of the amount of prior knowledge may pave the way towards a generation of estimators of more general applicability. This contribution introduces Description Logic extended by rules as a promising knowledge representation formalism for road and intersection understanding. We have set up a Description Logic knowledge base for arbitrary road and intersection geometries and configurations. Logically stated geometric constraints and road building regulations constrain the hypothesis space. Sensor data from an in-vehicle vision sensor and from a digital map provide evidence for a particular intersection. Partial observability and different abstraction layers of the input data are naturally handled by the representation formalism. Deductive inference services – namely satisfiability, classification, entailment, and consistency – are then used to narrow down the intersection hypothesis space based on the evidence and the background knowledge, and to retrieve intersection information relevant to a user, i.e. a human or a driver assistance system. We conclude with an outlook towards non-deductive reasoning, namely model construction under the answer set semantics.

Cite as

Britta Hummel, Werner Thiemann, and Irina Lulcheva. Scene Understanding of Urban Road Intersections with Description Logic. In Logic and Probability for Scene Interpretation. Dagstuhl Seminar Proceedings, Volume 8091, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{hummel_et_al:DagSemProc.08091.14,
  author =	{Hummel, Britta and Thiemann, Werner and Lulcheva, Irina},
  title =	{{Scene Understanding of Urban Road Intersections with Description Logic}},
  booktitle =	{Logic and Probability for Scene Interpretation},
  pages =	{1--16},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8091},
  editor =	{Anthony G. Cohn and David C. Hogg and Ralf M\"{o}ller and Bernd Neumann},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08091.14},
  URN =		{urn:nbn:de:0030-drops-16165},
  doi =		{10.4230/DagSemProc.08091.14},
  annote =	{Keywords: Autonomous Driving;, Road Recognition, Knowledge Representation, Description Logic, Nonmonotonic Reasoning}
}

Refine by Type
2 Document/PDF
1 Document/HTML

Refine by Publication Year
1 2025
1 2008

Refine by Author
1 Hummel, Britta
1 Igarashi, Ayumi
1 Kamiyama, Naoyuki
1 Lulcheva, Irina
1 Suksompong, Warut
Show More...

Refine by Series/Journal
1 LIPIcs
1 DagSemProc

Refine by Classification
1 Theory of computation → Algorithmic game theory
1 Theory of computation → Design and analysis of algorithms
1 Theory of computation → Problems, reductions and completeness

Refine by Keyword
1 Autonomous Driving;
1 Description Logic
1 Knowledge Representation
1 Nonmonotonic Reasoning
1 Road Recognition
Show More...

2 Search Results for "Hummel, Britta"

Reforming an Unfair Allocation by Exchanging Goods

Abstract

Cite as

Scene Understanding of Urban Road Intersections with Description Logic

Abstract

Cite as

Thanks for your feedback!

Could not send message