1
$\begingroup$

If we want to pick a solution $S$ from a collection of items $C$ to maximize some function $f(S)$.

The constraint that we pick at most $k$ item, i.e., $|S| \leq k$, is called the cardinality constraint.

If the items in $C$ belongs to different groups and we are allowed to picked at most $k_i$ items from group $i$, what is the right terminology for this constraint? I think some paper used to call it the group cardinality constraint but I'm not sure if it's still the popular terminology.

$\endgroup$
  • $\begingroup$ I'd say cardinality constraints are typically over a set of variables, e.g. Sudoku etc. So for me what you're describing is just a bunch of cardinality constraints. $\endgroup$ – Mikolas Oct 25 '17 at 17:27
  • $\begingroup$ "If the items in C belongs to different groups" => C is a multiset. Perhaps you can go with "multisets with cardinality constraints" or "cardinality constraints on multisets". $\endgroup$ – Marzio De Biasi Oct 25 '17 at 19:12
1
$\begingroup$

This is not clear from your question, but I am going to assume that the groups are disjoint. I.e. $C = \bigcup_i C_i$ and $C_i \cap C_j = \emptyset$ for every $i \neq j$. Then the collection of sets $\mathcal{S} = \{S \subseteq C: |S \cap C_i| = k_i \ \ \forall i\}$ is the collection of bases of a partition matroid. In the context of combinatorial optimization then the constraint $S \in \mathcal{S}$ is often called a partition constraint. This is a special case of matroid constraints. There is, for example, an extensive body of work on maximizing a submodular function $f(S)$ subject to matroid constraints, i.e. subject to the set $S$ being a basis of a matroid.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Yes, I was thinking about disjoint groups. $\endgroup$ – HTV Oct 25 '17 at 20:47
1
$\begingroup$

To be clear that I understand the context, I'm going to first reproduce you situation worded differently.

Consider a sequence of sets, $C_i$, and a target function, $f$. Let $\cup C_i=C$. We wish to find a subset $S\subseteq C$ that maximizes $f(S)$ under the constraint that $\forall i, |S\cap C_i|<k_i$ and $|S|<k$.

I would agree with the commenter that this should be referred to as a cardinality constraint or a collection of cardinality constraints. I might also call it a "structural constraint," but I would specifically avoid calling it a "group carnality constraint" as "group" already has a meaning. In general, I would advocate for avoiding referring to a collection as a "group," "set," or "class" unless your object actually satisfies the required axioms. "Collection" is a good, general word that doesn't have a mathematical meaning.

If you don't want to use the term "carnality constraint" you can always introduce a term to refer to this specific restriction in your context. This can be helpful because it allows you to highlight the context-sensitive meaning of the constraint in a way that a more general term doesn't. For example, I have a paper with a constraint of this form that I refer to as an "isolation condition" because, when $S$ satisfies it, $S$ is isolated from the structure of the rest of the graph in a relevant way. This gives me a simple and intuitive way to refer to the condition, while simultaneously telling the reader what is important about the condition every time it comes up.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I think it's fair to come up with a new terminology like you said. On the other hand, I want to make sure that I know the right or often used terminology for literature research as well. $\endgroup$ – HTV Oct 26 '17 at 1:21
  • $\begingroup$ @HTV Indeed, that was meant as a side comment and not the focus of my answer. $\endgroup$ – Stella Biderman Oct 26 '17 at 2:23

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.