Hot answers tagged

3

First, while the Gale-Shapely algorithm guarantees that at least one stable matching exists, it need not be unique$^*$. However, note that when the male-optimal and female-optimal matchings are the same, the stable matching is indeed unique, as shown in this answer. As the male-optimal and female-optimal matchings coincide, both can be considered the '...


2

You can find an answer to this in "Dynamic Planar Range Maxima Queries", by Brodal and Tsakalidis. They support insert and remove in $O(\log n)$ time. That paper points to several previous papers that addressed the question as well. In particular, I expect the simplest solution can be found in sections 8 and 9 of "Maintenance of Configurations in the Plane",...


1

Here is one approach you could consider. If the number of non-missing coordinates is tightly concentrated around 10, it might help you partly avoid the curse of dimensionality. I don't know whether it will be useful in practice. Choose a random hash function $h:\{1,\dots,d\} \to \{1,\dots,10\}$. If $x \in \mathbb{R}^d$ is a data point, let $f(x)$ be its ...


1

A multi-objective optimization problem can be formulated as \begin{align} \min\limits_{\phi \in \Phi} & \quad [f_1(\phi), f_2(\phi), \ldots, f_m(\phi)]^T \label{eq:mo-objectives} \\ s.t. & \quad g_j(\phi) \leqslant 0,~j = 1, \ldots, J \label{eq:mo-constraints} \end{align} Without loss of generality, assume that all objective functions are ...


Only top voted, non community-wiki answers of a minimum length are eligible