Source author record

Yohai Trabelsi

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

ResearcherUnclaimed source record

Artificial Intelligence Computational Geometry

Catalog footprint

Research overview

2works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Resource Allocation to Agents with Restrictions: Maximizing Likelihood with Minimum Compromise

Many scenarios where agents with restrictions compete for resources can be cast as maximum matching problems on bipartite graphs. Our focus is on resource allocation problems where agents may have restrictions that make them incompatible with some resources. We assume that a Principle chooses a maximum matching randomly so that each agent is matched to a resource with some probability. Agents would like to improve their chances of being matched by modifying their restrictions within certain limits. The Principle's goal is to advise an unsatisfied agent to relax its restrictions so that the total cost of relaxation is within a budget (chosen by the agent) and the increase in the probability of being assigned a resource is maximized. We establish hardness results for some variants of this budget-constrained maximization problem and present algorithmic results for other variants. We experimentally evaluate our methods on synthetic datasets as well as on two novel real-world datasets: a vacation activities dataset and a classrooms dataset.

preprint2012arXiv

Bottleneck Non-Crossing Matching in the Plane

Let $P$ be a set of $2n$ points in the plane, and let $M_{\rm C}$ (resp., $M_{\rm NC}$ ) denote a bottleneck matching (resp., a bottleneck non-crossing matching) of $P$ . We study the problem of computing $M_{\rm NC}$ . We first prove that the problem is NP-hard and does not admit a PTAS. Then, we present an $O(n^{1.5}\log^{0.5} n)$ -time algorithm that computes a non-crossing matching $M$ of $P$ , such that $bn(M) \le 2\sqrt{10} \cdot bn(M_{\rm NC})$ , where $bn(M)$ is the length of a longest edge in $M$ . An interesting implication of our construction is that $bn(M_{\rm NC})/bn(M_{\rm C}) \le 2\sqrt{10}$ .

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.