Finding the optimal placement of weights on a circle

Clash Royale CLAN TAG#URR8PPP

up vote
4
down vote

favorite

I'm wondering if anyone knows any efficient algorithms for finding the optimal placement of weights around a circle to minimize the center of mass. The mathematical formulation is as follows:

$$min_sigmain S_n left|sum_k=0^n-1 m_sigma(k) e^frac2pi iknright|^2,$$ where $S_n$ is the set of permutations on $n$ elements and weights $m_0,m_1,...,m_n-1inmathbbR$ are given. The context is an engineering problem, so if there is a heuristic or stochastic method that gives a near optimal solution that would be fine.

I've considered a brute force check, but the number of permutations one would need to check to be comprehensive is $frac(n-1)!2$ (considering the fact that reflections and rotations give the same weight distribution).

optimization extremal-combinatorics

share|cite|improve this question

edited Jul 19 at 2:11

asked Jul 18 at 22:47

mheldman

51116

add a comment | 

up vote
4
down vote

favorite

I'm wondering if anyone knows any efficient algorithms for finding the optimal placement of weights around a circle to minimize the center of mass. The mathematical formulation is as follows:

$$min_sigmain S_n left|sum_k=0^n-1 m_sigma(k) e^frac2pi iknright|^2,$$ where $S_n$ is the set of permutations on $n$ elements and weights $m_0,m_1,...,m_n-1inmathbbR$ are given. The context is an engineering problem, so if there is a heuristic or stochastic method that gives a near optimal solution that would be fine.

I've considered a brute force check, but the number of permutations one would need to check to be comprehensive is $frac(n-1)!2$ (considering the fact that reflections and rotations give the same weight distribution).

optimization extremal-combinatorics

share|cite|improve this question

edited Jul 19 at 2:11

asked Jul 18 at 22:47

mheldman

51116

add a comment | 

up vote
4
down vote

favorite

up vote
4
down vote

favorite

I'm wondering if anyone knows any efficient algorithms for finding the optimal placement of weights around a circle to minimize the center of mass. The mathematical formulation is as follows:

$$min_sigmain S_n left|sum_k=0^n-1 m_sigma(k) e^frac2pi iknright|^2,$$ where $S_n$ is the set of permutations on $n$ elements and weights $m_0,m_1,...,m_n-1inmathbbR$ are given. The context is an engineering problem, so if there is a heuristic or stochastic method that gives a near optimal solution that would be fine.

I've considered a brute force check, but the number of permutations one would need to check to be comprehensive is $frac(n-1)!2$ (considering the fact that reflections and rotations give the same weight distribution).

optimization extremal-combinatorics

share|cite|improve this question

edited Jul 19 at 2:11

asked Jul 18 at 22:47

mheldman

51116

I'm wondering if anyone knows any efficient algorithms for finding the optimal placement of weights around a circle to minimize the center of mass. The mathematical formulation is as follows:

$$min_sigmain S_n left|sum_k=0^n-1 m_sigma(k) e^frac2pi iknright|^2,$$ where $S_n$ is the set of permutations on $n$ elements and weights $m_0,m_1,...,m_n-1inmathbbR$ are given. The context is an engineering problem, so if there is a heuristic or stochastic method that gives a near optimal solution that would be fine.

I've considered a brute force check, but the number of permutations one would need to check to be comprehensive is $frac(n-1)!2$ (considering the fact that reflections and rotations give the same weight distribution).

optimization extremal-combinatorics

share|cite|improve this question

edited Jul 19 at 2:11

asked Jul 18 at 22:47

mheldman

51116

share|cite|improve this question

share|cite|improve this question

edited Jul 19 at 2:11

edited Jul 19 at 2:11

edited Jul 19 at 2:11

asked Jul 18 at 22:47

mheldman

51116

asked Jul 18 at 22:47

mheldman

51116

asked Jul 18 at 22:47

mheldman

51116

51116

add a comment | 

add a comment | 

1 Answer
1

active

oldest

votes

up vote
3
down vote

This is a "2-dimensional" variant of the partition problem (in a nutshell: split a set of numbers as evenly as possible). As such, on the one hand the problem seems NP-hard; on the other hand it seems that the approximation schemes for the partition problem should not be too hard to adapt.

share|cite|improve this answer

answered Jul 18 at 23:26

Anonymous

4,8033940

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',
convertImagesToLinks: true,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
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

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2856093%2ffinding-the-optimal-placement-of-weights-on-a-circle%23new-answer', 'question_page');

);

Post as a guest

Name Email

1 Answer
1

active

oldest

votes

1 Answer
1

active

oldest

votes

active

oldest

votes

active

oldest

votes

up vote
3
down vote

This is a "2-dimensional" variant of the partition problem (in a nutshell: split a set of numbers as evenly as possible). As such, on the one hand the problem seems NP-hard; on the other hand it seems that the approximation schemes for the partition problem should not be too hard to adapt.

share|cite|improve this answer

answered Jul 18 at 23:26

Anonymous

4,8033940

add a comment | 

up vote
3
down vote

This is a "2-dimensional" variant of the partition problem (in a nutshell: split a set of numbers as evenly as possible). As such, on the one hand the problem seems NP-hard; on the other hand it seems that the approximation schemes for the partition problem should not be too hard to adapt.

share|cite|improve this answer

answered Jul 18 at 23:26

Anonymous

4,8033940

add a comment | 

up vote
3
down vote

up vote
3
down vote

This is a "2-dimensional" variant of the partition problem (in a nutshell: split a set of numbers as evenly as possible). As such, on the one hand the problem seems NP-hard; on the other hand it seems that the approximation schemes for the partition problem should not be too hard to adapt.

share|cite|improve this answer

answered Jul 18 at 23:26

Anonymous

4,8033940

This is a "2-dimensional" variant of the partition problem (in a nutshell: split a set of numbers as evenly as possible). As such, on the one hand the problem seems NP-hard; on the other hand it seems that the approximation schemes for the partition problem should not be too hard to adapt.

share|cite|improve this answer

answered Jul 18 at 23:26

Anonymous

4,8033940

share|cite|improve this answer

share|cite|improve this answer

answered Jul 18 at 23:26

Anonymous

4,8033940

answered Jul 18 at 23:26

Anonymous

4,8033940

answered Jul 18 at 23:26

Anonymous

4,8033940

4,8033940

add a comment | 

add a comment | 

 

draft saved

draft discarded

 

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

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2856093%2ffinding-the-optimal-placement-of-weights-on-a-circle%23new-answer', 'question_page');

);

Post as a guest

Name Email

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

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

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

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Name Email

Name

Email

Name Email

Name

Email