Fdtxjr

How to manage monthly salary

Why was the "bread communication" in the arena of Catching Fire left out in the movie?

Landing in very high winds

What is the offset in a seaplane's hull?

Is this food a bread or a loaf?

LWC and complex parameters

Patience, young "Padovan"

What does "enim et" mean?

What causes the sudden spool-up sound from an F-16 when enabling afterburner?

Extreme, but not acceptable situation and I can't start the work tomorrow morning

How could a lack of term limits lead to a "dictatorship?"

Manga about a female worker who got dragged into another world together with this high school girl and she was just told she's not needed anymore

Could a US political party gain complete control over the government by removing checks & balances?

Finding files for which a command fails

How can I plot a Farey diagram?

Is every set a filtered colimit of finite sets?

I’m planning on buying a laser printer but concerned about the life cycle of toner in the machine

aging parents with no investments

If a centaur druid Wild Shapes into a Giant Elk, do their Charge features stack?

Symmetry in quantum mechanics

Is there any use for defining additional entity types in a SOQL FROM clause?

Lied on resume at previous job

How is it possible for user's password to be changed after storage was encrypted? (on OS X, Android)

Re-submission of rejected manuscript without informing co-authors

Finding the optimal bijective map between two sets of natural numbers

A variant of assignment problem (different sizes of sets)Facets of the convex hull as solution of an optimization problem?Optimal paths between two closed linesHow to find the optimal mapping between two sets?Proof of Optimality for Approximation of Probability Spaces by PCASelect matrices to maximize their productOptimal Rotation between two sets of pointsOptimizing a stability function that has no closed formNumber of injective, surjective, bijective functions.Bipartite allocation with minimum cost

0

$begingroup$

I have two sets $A$ and $B$, each containing $N$ high-dimensional vectors.
I have an $Ntimes N$ matrix, $M$, where $M_i,j=textDist||A_i,B_j||$.

I am trying to find a bijective map $Arightarrow B$ that minimises the average distance between paired elements.

The surjective case is obviously trivial; just map $A_i$ to $B_j$ where $j=textargmax(M_i,j)$. However I want a 1-to-1 mapping.

$N$ is not very large (~5), but I have many such pairs and need to find an algorithm in order to automate the process.

Any help appreciated!

combinatorics matrices optimization

share|cite|improve this question

asked Mar 22 at 16:13

JoshDJoshD

136

$endgroup$

add a comment | 

0

$begingroup$

I have two sets $A$ and $B$, each containing $N$ high-dimensional vectors.
I have an $Ntimes N$ matrix, $M$, where $M_i,j=textDist||A_i,B_j||$.

I am trying to find a bijective map $Arightarrow B$ that minimises the average distance between paired elements.

The surjective case is obviously trivial; just map $A_i$ to $B_j$ where $j=textargmax(M_i,j)$. However I want a 1-to-1 mapping.

$N$ is not very large (~5), but I have many such pairs and need to find an algorithm in order to automate the process.

Any help appreciated!

combinatorics matrices optimization

share|cite|improve this question

asked Mar 22 at 16:13

JoshDJoshD

136

$endgroup$

add a comment | 

$begingroup$

I have two sets $A$ and $B$, each containing $N$ high-dimensional vectors.
I have an $Ntimes N$ matrix, $M$, where $M_i,j=textDist||A_i,B_j||$.

I am trying to find a bijective map $Arightarrow B$ that minimises the average distance between paired elements.

The surjective case is obviously trivial; just map $A_i$ to $B_j$ where $j=textargmax(M_i,j)$. However I want a 1-to-1 mapping.

$N$ is not very large (~5), but I have many such pairs and need to find an algorithm in order to automate the process.

Any help appreciated!

combinatorics matrices optimization

share|cite|improve this question

asked Mar 22 at 16:13

JoshDJoshD

136

$endgroup$

share|cite|improve this question

asked Mar 22 at 16:13

JoshDJoshD

136

share|cite|improve this question

asked Mar 22 at 16:13

JoshDJoshD

136

asked Mar 22 at 16:13

JoshDJoshD

136

asked Mar 22 at 16:13

JoshDJoshD

136

1 Answer
1

active

oldest

votes

1

$begingroup$

This is called an Assignment problem. You can formulate you problem as the following integer program:

$$
min sum_i=1^Nsum_j=1^N x_ij M_ij \
s.t. sum_i=1^Nx_ij = 1 ;forall j in N \
sum_j=1^Nx_ij = 1 ; forall i in N \
0 leq x_ij leq 1 ;forall iin N,j in N \
x_ij in mathbbZ ;forall iin N,j in N
$$

This problem can be solved by solving the linear relaxation of the above IP (drop the integer constraint) with e.g. the Simplex Method.

share|cite|improve this answer

edited Mar 22 at 17:10

answered Mar 22 at 17:00

wiluqawiluqa

365

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Thank you this was the information I needed. Knowing the correct terminology for my problem allowed me to find a handy one-line implementation of the simplex method, and has solved my problem.
  $endgroup$
  – JoshD
  Mar 22 at 17:20
  

  
  
  
  

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3158338%2ffinding-the-optimal-bijective-map-between-two-sets-of-natural-numbers%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

1

$begingroup$

This is called an Assignment problem. You can formulate you problem as the following integer program:

$$
min sum_i=1^Nsum_j=1^N x_ij M_ij \
s.t. sum_i=1^Nx_ij = 1 ;forall j in N \
sum_j=1^Nx_ij = 1 ; forall i in N \
0 leq x_ij leq 1 ;forall iin N,j in N \
x_ij in mathbbZ ;forall iin N,j in N
$$

This problem can be solved by solving the linear relaxation of the above IP (drop the integer constraint) with e.g. the Simplex Method.

share|cite|improve this answer

edited Mar 22 at 17:10

answered Mar 22 at 17:00

wiluqawiluqa

365

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Thank you this was the information I needed. Knowing the correct terminology for my problem allowed me to find a handy one-line implementation of the simplex method, and has solved my problem.
  $endgroup$
  – JoshD
  Mar 22 at 17:20
  

  
  
  
  

add a comment | 

1

$begingroup$

This is called an Assignment problem. You can formulate you problem as the following integer program:

$$
min sum_i=1^Nsum_j=1^N x_ij M_ij \
s.t. sum_i=1^Nx_ij = 1 ;forall j in N \
sum_j=1^Nx_ij = 1 ; forall i in N \
0 leq x_ij leq 1 ;forall iin N,j in N \
x_ij in mathbbZ ;forall iin N,j in N
$$

This problem can be solved by solving the linear relaxation of the above IP (drop the integer constraint) with e.g. the Simplex Method.

share|cite|improve this answer

edited Mar 22 at 17:10

answered Mar 22 at 17:00

wiluqawiluqa

365

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Thank you this was the information I needed. Knowing the correct terminology for my problem allowed me to find a handy one-line implementation of the simplex method, and has solved my problem.
  $endgroup$
  – JoshD
  Mar 22 at 17:20
  

  
  
  
  

add a comment | 

$begingroup$

This is called an Assignment problem. You can formulate you problem as the following integer program:

$$
min sum_i=1^Nsum_j=1^N x_ij M_ij \
s.t. sum_i=1^Nx_ij = 1 ;forall j in N \
sum_j=1^Nx_ij = 1 ; forall i in N \
0 leq x_ij leq 1 ;forall iin N,j in N \
x_ij in mathbbZ ;forall iin N,j in N
$$

This problem can be solved by solving the linear relaxation of the above IP (drop the integer constraint) with e.g. the Simplex Method.

share|cite|improve this answer

edited Mar 22 at 17:10

answered Mar 22 at 17:00

wiluqawiluqa

365

$endgroup$

share|cite|improve this answer

edited Mar 22 at 17:10

answered Mar 22 at 17:00

wiluqawiluqa

365

answered Mar 22 at 17:00

wiluqawiluqa

365

answered Mar 22 at 17:00

wiluqawiluqa

365