Source author record

Andrei Asinowski

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Discrete Mathematics Computational Complexity Computational Geometry Computer Science and Game Theory

Catalog footprint

Research overview

3works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Counting Houses of Pareto Optimal Matchings in the House Allocation Problem

Let $A,B$ with $|A| = m$ and $|B| = n\ge m$ be two sets. We assume that every element $a\in A$ has a reference list over all elements from $B$ . We call an injective mapping $τ$ from $A$ to $B$ a matching. A blocking coalition of $τ$ is a subset $A'$ of $A$ such that there exists a matching $τ'$ that differs from $τ$ only on elements of $A'$ , and every element of $A'$ improves in $τ'$ , compared to $τ$ according to its preference list. If there exists no blocking coalition, we call the matching $τ$ an exchange stable matching (ESM). An element $b\in B$ is reachable if there exists an exchange stable matching using $b$ . The set of all reachable elements is denoted by $E^*$ . We show $|E^*| \leq \sum_{i = 1,\ldots, m}{\left\lfloor\frac{m}{i}\right\rfloor} = Θ(m\log m).$ This is asymptotically tight. A set $E\subseteq B$ is reachable (respectively exactly reachable) if there exists an exchange stable matching $τ$ whose image contains $E$ as a subset (respectively equals $E$ ). We give bounds for the number of exactly reachable sets. We find that our results hold in the more general setting of multi-matchings, when each element $a$ of $A$ is matched with $\ell_a$ elements of $B$ instead of just one. Further, we give complexity results and algorithms for corresponding algorithmic questions. Finally, we characterize unavoidable elements, i.e., elements of $B$ that are used by all ESM's. This yields efficient algorithms to determine all unavoidable elements.

preprint2014arXiv

Disjoint compatibility graph of non-crossing matchings of points in convex position

Let $X_{2k}$ be a set of $2k$ labeled points in convex position in the plane. We consider geometric non-intersecting straight-line perfect matchings of $X_{2k}$ . Two such matchings, $M$ and $M'$ , are disjoint compatible if they do not have common edges, and no edge of $M$ crosses an edge of $M'$ . Denote by $\mathrm{DCM}_k$ the graph whose vertices correspond to such matchings, and two vertices are adjacent if and only if the corresponding matchings are disjoint compatible. We show that for each $k \geq 9$ , the connected components of $\mathrm{DCM}_k$ form exactly three isomorphism classes -- namely, there is a certain number of isomorphic small components, a certain number of isomorphic medium components, and one big component. The number and the structure of small and medium components is determined precisely.

preprint2014arXiv

Triangulations with few ears: symmetry classes and disjointness

An ear in a triangulation $T$ of a convex $n$ -gon $P$ is a triangle of $T$ that shares two sides with $P$ itself. Certain enumerational and structural problems become easier when one considers only triangulations with few ears. We demonstrate this in two ways. First, for $k=2, 3$ , we find the number of symmetry classes of triangulations with $k$ ears. Second, for $k=2, 3$ , we determine the number of triangulations disjoint from a given triangulation: this number depends only on $n$ for $k=2$ , and only on lengths of branches of the dual tree for $k=3$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.