Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

You are given a set $A$ of integers of size $n$ and a common divisor $r$ called the "anchor", which isn't in $A$ and isn't necessarily the greatest common divisor, either. Let $M$ be the least common multiple of all elements in $A$. The cost of $A$ is then defined as $\frac{M}{r} \cdot n$.

For example, if $A = \{25, 30, 50\}$ and $5$ is the anchor, the cost will be $\frac{150}{5} \cdot 3 = 90$.

You want to minimize the cost of $A$. In order to reduce the cost of $A$, you can "spin off" $A$ by creating a set $S$ and moving $k$ elements from $A$ there, which must be divisible by some element $a\in A$ where $a > r$. The element $a$ becomes the anchor of $S$, which cannot be in $S$. The cost of $S$ is then $\frac{M}{a} \cdot k$. $S$ and $A$ after spin-off must be mutually exclusive. The cost of $A$ after spin-off is the sum of the costs of $A$ and all of its spin off sets.

For example, if you spin off $A$ by defining $S$ to be $\{50\}$, $A$ would be left with just $\{25, 30\}$. The cost of $A$ after spin-off would be $\frac{150}{5} \cdot (3 - 1) = 60$ and the cost of $S$ would be $\frac{150}{25} \cdot 1 = 6$. The total cost of $A$ would be $60 + 6 = 66$, which is smaller than $A$ before spin-off.

You can spin off $S$ and in turn spin off its own spin-off sets and so on. You can also add an element to a set to serve as the anchor of its spin-off set.

For example, if $A = \{20, 30, 50\}$ and $5$ is the anchor, the cost will be $\frac{300}{5} \cdot 3 = 180$. However, if you spin $A$ off by adding $10$ and moving the rest, you will have $A = \{10\}$ and $S = \{20, 30, 50\}$. The cost of $A$ after spin-off is $\frac{300}{5} \cdot 1 = 60$ and $S$ is $\frac{300}{10} \cdot 3 = 90$, for a total of $150$.

The goal is to minimize the total cost of $A$ by spinning it off, recursively if necessary.

How do you go about doing this? Is this a non-linear optimization problem?

This is not homework. I'm a programmer and this is actually for my work which I've abstracted. I've taken a few university level math courses like $10$ years ago, but I barely remember high-school math now...

Thank you in advance.

share|improve this question
    
There are some things which are not clear. In your second example, you are adding the element 10 and then spinning off the set S. Are there any conditions or constraints on this operation? In your first example you don't add any elements and that might make a big difference. Also, how is the anchor value selected for the spin-off subsets? Can you explain how the set S has an anchor of 25 in example 1 and 10 in case 2? –  svenkatr Jan 6 '12 at 18:55
    
The only constraint to adding an element is that it must be a common divisor of the spin-off set. You're right that I could've added an element in the first example, but I didn't just to show how to calculate the cost of A without spinning off. An anchor should be selected to reduce the total cost of A. The larger, the better normally. I chose 25 as the anchor of the spin-off set in the first example because it happens to lead to the optimal cost of A. The same with the second example. 10 would give you the optimal total cost of A. Thanks. –  Tom Tucker Jan 6 '12 at 19:05
    
"The question is widely applicable to a large audience."?! –  joriki Jan 11 '12 at 1:19
    
You seem to define many operations... your notion of "spinning" is very vague ; it seems there are many ways to do it. Is there any way you can make things more clear or perhaps tell us where does your intuition come from to define such operations on those sets? The choice of word "spinning" seems vague, also. –  Patrick Da Silva Jan 12 '12 at 2:59
    
I'm confused by just the first sentence. "a common divisor r called the "anchor", which isn't in A and isn't necessarily the greatest common divisor, either." Are you trying to define a function, namely: $f(r)=\frac{Mn}{r}$ where $r$ has to be a divisor which isn't in set A and can be, but is not restricted to being, the common greatest common divisor? If you wish to minimize $f(r)$ (the cost of $A$), the math begs that you restrict $r$ to being the greatest common divisor. I apologize, but this is the most help (if I am helping) that I can give. You lost me entirely in the 2nd paragraph. –  000 Jan 15 '12 at 7:38
add comment

1 Answer 1

up vote 1 down vote accepted
+50

If I understand the question correctly, a solution to the problem will have the form of a (rooted) tree. Each vertex of the tree will be labeled with a set of positive integers, which is either what remains of $A$, at the root, or a spin-off of $A$, a spin-off of a spin-off of $A$, etc. at vertices which are not the root. The sets of positive integers must fulfill the following constraints:

(1) They are nonempty and disjoint;

(2) All integers in all sets divide the original lcm, $M$;

(3) The union of the sets contains the original set $A$;

(4) For each set, its gcd is divisible by its anchor, which is a member of the set at its parent vertex (if the set is not at the root) or a fixed, given, number $r$ not appearing in any set (if the set is at the root.)

Given such a tree, its cost is $M \sum_v (\#S_v)/a_v$, where $v$ ranges over the vertices of the tree, $S_v$ is the set at vertex $v$, and $a_v$ is the anchor of the set at vertex $v$.

First, observe that if a vertex is labeled with a set of size larger than 1, $\{c_1,\ldots,c_t\}$, say, we can split it into $t$ vertices, labeled with $\{c_1\}$, $\{c_2\}$, $\dots$, $\{c_t\}$, and reapportion its child vertices among these vertices so that each child set is beneath its anchor. This does not change the cost of the tree, so after doing this repeatedly, we may assume that all sets have size 1, i.e., each vertex is labeled with a single number. Second, observe that we may add a vertex above the root labeled with the original anchor. These two steps reduce the problem to the problem of finding a rooted tree whose vertices are labeled with distinct positive integers which satisfies

(a) All labels divide $M$;

(b) The root is labeled with $r$, the original anchor;

(c) The set of labels contains the original set $A$; and

(d) the label at the top of each edge divides the label at the bottom,

and which has minimum cost, where the cost is now $M$ times the sum over all edges of the reciprocal of the label at the top of the edge. Also, we may now allow $r$ to be a member of $A$, and we observe that there is no need to require the vertex labels to be distinct, since if we had two vertices with the same label, we could construct a cheaper tree by deleting one of them and reapportioning all its children to the other.

Let $T$ be an minimum-cost tree for $r$, $M$ and $A$. Observe that:

(i) Each of the leaves of $T$ must be labeled with a member of $A$, since otherwise we could construct a cheaper tree by removing a leaf.

(ii) If a vertex other than the root has exactly 1 child, it must be labeled with a member of $A$, since otherwise it would be cheaper to remove the vertex and reapportion its child to its parent.

(iii) If a vertex other than the root has 2 or more children and is not labeled with a member of $A$, we can assume that its label equals the gcd of the labels of its children, since otherwise we could make a cheaper tree by relabeling it with the gcd of the labels of its children.

(iv) Fix some parent vertex $v$ of leaves, and let it have label $l$ and leaf children $w_1$, $\ldots$, $w_t$ with labels $s_1$, $\ldots$, $s_t$. Then if we delete $w_1$, $\ldots$, $w_t$ from $T$, the remaining tree, $T'$, must be minimum-cost for $r$, $M$, and the set $A\cup\{l\}\setminus\{s_1,\ldots,s_t\}$, since if there was a cheaper tree, $T''$, say, for this set, we could make a tree cheaper than $T$ for $A$ by attaching the children $w_1$, $\ldots$, $w_t$ to the vertex labeled $l$ in $T''$.

Rules (i)-(iv) give us a recursive algorithm for finding an optimal tree $T$. If $A$ is empty or $A=\{r\}$, we are done since the optimal tree consists of only the root vertex and has cost 0. Otherwise, $T$ must have at least one leaf, and since, by (i), all leaves are labeled with a member of $A$, there must be some subset $\emptyset\ne S\subseteq A$ and some vertex $v$ such that $v$ has only leaf children and $S$ contains the set of labels of the set of leaves, $W$, which are children of $v$. Then, by (ii) and (iii), the label of $v$, $l$, must be either $r$, some member of $A$, or $\gcd(S)$. Now, let $T'$ be $T$ with the vertices in $W$ removed; by (iv), we can compute $T'$ by calling the algorithm again to find an optimal tree for $A\cup\{l\}\setminus S$, and then $T$ can be reconstructed by reattaching the children $W$ to $v$. Performing this step for all possible choices of $S$ and $l$ will give a set of possibilities for $T$ from which we can take the best possible answer.

share|improve this answer
    
For your answer to be worth something, the question needs to be made more clear... I can't tell if what you're doing is right or wrong because I can't understand the question. Sorry –  Patrick Da Silva Jan 12 '12 at 3:04
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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