For a set $X$ by $B(X)$ we denote the family of all finite subsets of $X$ endowed with the operation $\oplus$ of symmetric difference. This operation turns $B(X)$ into a Boolean group, which can be identified with the free Boolean group over $X$.

Let us recall that a group is Boolean if each its element has order at most 2.

The group $B(X)$ contains a subgroup $B_0(X)$ of index two, consisting of sets of even cardinality.

Each metric $d$ on $X$ determines the Graev metric $\hat d$ on $B_0(X)$ defined as $$\hat d(A,B)=\inf\sum_{i=1}^kd(x_i,y_i)$$ where the infimum is taken over all partitions of the symmetric difference $A\oplus B$ into pairwise disjoint doubletons $\{x_1,y_1\},\dots,\{x_k,y_k\}$.

This definition suggests a brute force algorithm for calculation of the Graev distance $\hat d(A,B)$: Let $k=\frac12|A\oplus B|$ and compare the sums for all possible $\frac{(2k)!}{2^kk!}$ partitions of $A\oplus B$ into $k$ doubletons.

Unfortunately such algorithm has (more than) exponential complexity.

Question. Is there a more simple (for example, polynomial time) algorithm for calculating the Graev distance on $B_0(X)$?

Remark. It seems that the naive approach (to find the shortest doubleton in $A\oplus B$, delete it, find next shortest etc), does not work.

  • $\begingroup$ Just to streamline notation, you have $\hat{d}(A,B)=\ell(A\oplus B)$, where you can call $\ell(A)=\hat{d}(\emptyset,A)$ the Graev length of $A$. The question is about computing $\ell(A)$. $\endgroup$ – YCor Feb 1 at 19:20
  • $\begingroup$ As I said, this reduces to a question with no reference to the symmetric difference and hence no group theory. It's a combinatorial optimization problem. I would rephrase more concisely the question in this way (and tag combinatorial-optimization) to hope for optimal feedback: "Let $X$ be a finite set of finite even cardinal. For every metric $d$ on $X$, define $L(d)$ as (...). How to compute $L(d)$?" $\endgroup$ – YCor Feb 1 at 23:01

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.