0
$\begingroup$

Let $C$ be the set of all available classes, $S$ be the set of all available students, $P$ be the set of all available phone numbers.

Each student many have zero to many phone numbers, but each phone number can only belong to zero or one student. There may have little chance that some phone numbers have no owners at all. To formalize this relationship, there exists a mapping $f:S \to 2^P$, where $2^P$ is the power set, or set of subsets of $P$. In addition, $\underset{s \in S}{\bigcup} f(s) \subseteq P$, and $\forall s_i, s_j \in S$ where $i \ne j$, $f(s_i) \cap f(s_j) = \emptyset$.

Each class can have zero to many students, and each student can take zero to many classes. To formalize this relationship, there exists mappings $g:C \to 2^S$ and $h:S \to 2^C$. In addition, followings hold:

  • $\underset{c \in C}{\bigcup} g(c) \subseteq S$
  • $\forall c_i, c_j \in C$ where $i \ne j, g(c_i) \cap g(c_j) \in 2^S$
  • $\underset{s \in S}{\bigcup} h(s) \subseteq C$
  • $\forall s_i, s_j \in S$ where $i \ne j, h(s_i) \cap h(s_j) \in 2^C$

Now we have a data set contains records for each class $c \in C$, a subset of students in that class $\sigma \in 2^{g(c) \cup \epsilon_\sigma}$, and a subset of phone numbers owned by all the students in that class $\phi \in 2^{\underset{s \in g(c)}{\bigcup} f(s) \cup \epsilon_\phi}$.

Note that $\epsilon_\sigma$ and $\epsilon_\phi$ are error sets explained later.

Thus, the whole data set is given by

$\{ (c,\sigma,\phi) | c \in C, \sigma \in 2^{g(c) \cup \epsilon_\sigma}, \phi \in 2^{\underset{s \in g(c)}{\bigcup} f(s) \cup \epsilon_\phi} \}$

  • For a class $c \in C$, there may have little chance that a student actually taking the class $s \in g(c)$ not appeared on the record, $s \notin \sigma$. Thus, we used the notation $\sigma \in 2^{g(c)}$ to denote such absence.
  • For a class $c \in C$, a student in the class $s \in g(c)$ usually only provides zero or one of his phone numbers, but there may have some odds that a student provided more than one phone numbers on the record.
  • For a class $c \in C$, there may have little chance that a student not taking the class $s \notin g(c)$ actually appeared on the record, $s \in \sigma$. Thus, we used an error set $\epsilon_\sigma$ to accommodate such odds.
  • For a class $c \in C$, there may have little chance that a phone number $p \in P$ not belong to any student in the class $p \notin \underset{s \in g(c)}{\bigcup} f(s)$ actually appeared on the record, $p \in \phi$. Thus, we used an error set $\epsilon_\phi$ to accommodate such odds.

Now, we want to find a matching algorithm, let's say, $M:S \to 2^P$. $M$ takes any student $s \in S$, and outputs a set of phone numbers $\Phi \in 2^P$ that seems to have high probability of belonging to $s$, that is, $\forall p \in \Phi, \mathrm{P}(p \in f(s)) \gg \mathrm{P}(p' \in f(s))$ for any $p' \notin \Phi$.

The problem is approximately similar to finding relationships $f$ between $S$ and $P$, given a bijection relationship between their cosets to another set $C$, $\psi : S/C \to P/C$.

I already know a way to implement this algorithm, but I want to know what category of problems it is, or what type of algorithm it’s called, in order to find some papers or implementations for optimizations.

$\endgroup$
  • $\begingroup$ I don't understand what "There may have little chance" means. You're asking about finding a set that has a high probability, but you haven't told us what the probability distributions are or what the random process is, so I don't think the question is well-specified. $\endgroup$ – D.W. Oct 17 '17 at 6:09
  • $\begingroup$ @D.W. "There may have little chance" means strictly less than 1%. It's used for completeness of the question to include some corner cases to make it more general. The exact probability distributions are of course unknown, but I don't think that would be a problem because of CLT. $\endgroup$ – Rix Oct 18 '17 at 3:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.