ﻻ يوجد ملخص باللغة العربية
A matching in a bipartite graph $G:=(X + Y,E)$ is said to be envy-free if no unmatched vertex in $X$ is adjacent to a mathced vertex in $Y$. Every perfect matching is envy-free, but envy-free matchings may exist even when perfect matchings do not. We provide a polynomial-time algorithm for finding an envy-free matching of maximum cardinality. For edge-weighted bipartite graphs, we provide a polynomial-time algorithm for finding a maximum-cardinality envy-free matching of minimum weight. We show how envy-free matchings can be used in various fair division problems with either continuous resources (cakes) or discrete ones. In particular, we show a symmetric algorithm for proportional cake-cutting, an algorithm for $1$-out-of-$(2n-2)$ maximin-share allocation of discrete goods, and an algorithm for $1$-out-of-$lfloor 2n/3rfloor$ maximin-share allocation of discrete bads (chores) among $n$ agents.
In this paper we further investigate the well-studied problem of finding a perfect matching in a regular bipartite graph. The first non-trivial algorithm, with running time $O(mn)$, dates back to K{o}nigs work in 1916 (here $m=nd$ is the number of ed
We consider the well-studied problem of finding a perfect matching in $d$-regular bipartite graphs with $2n$ vertices and $m = nd$ edges. While the best-known algorithm for general bipartite graphs (due to Hopcroft and Karp) takes $O(m sqrt{n})$ time
In this paper we study envy-free division problems. The classical approach to such problems, used by David Gale, reduces to considering continuous maps of a simplex to itself and finding sufficient conditions for this map to hit the center of the sim
We study the fair division of items to agents supposing that agents can form groups. We thus give natural generalizations of popular concepts such as envy-freeness and Pareto efficiency to groups of fixed sizes. Group envy-freeness requires that no g
We study the computational complexity of two well-known graph transversal problems, namely Subset Feedback Vertex Set and Subset Odd Cycle Transversal, by restricting the input to $H$-free graphs, that is, to graphs that do not contain some fixed gra