Results 1 to 2 of 2

Math Help - Balanced Mancala Problem

  1. #1
    Member
    Joined
    Jan 2009
    Posts
    94

    Balanced Mancala Problem

    The problem statement is very long. Here it goes:
    We have stones coming in batches. Each stone has a color and a weight. If the color of a stone is:
    Yellow:
    It must be placed every other pit (every 2 pits)
    Batch size is always: 6
    Total batches: y
    Total number = 6y

    Red:
    Must be placed every 3 pits
    Batch size: 4
    Total batches: r
    Total number = 4r

    Green:
    Must be placed every 4 pits
    Batch size: 3
    Total batches: g
    Total numbers = 3g

    Blue:
    Must be placed every 6 pits
    Batch size: 2
    Total batches: b
    Total number = 2b

    Purple:
    Must be placed only once in 12 pits
    Batch size: 1
    Total batches: p
    Total numbers = p

    So there are N=6y+4r+3g+2b+p many stones. The stones in the same batch have the same weight. Different batches may have different weights. WLOG, assume that all weights are integers.

    We have a proof that ending up with the best well-balanced mancala is very difficult (NP-Hard). Here "well-balanced" means that the pit with the maximum weight is minimized when all stones are distributed. Let's call this maximum pit weight as W.

    Consider the following heuristic process:
    Step 1. Sort the batches with respect to their weights (batches with the high-weight stones go first)
    Step 2. Insert the first batch starting from pit number 1.
    Step 3. Insert the next batch in a way that the total maximum weight throughout 12 pits remains minimum.
    Step 4. Repeat Step 3 until all batches are placed in the mancala. Let H be the maximum weight throughout 12 pits.

    A simple Example:
    Suppose we have only 4 batches:
    Yellow (6 stones, each 45 grams)
    Blue (2 stones, each 40 grams)
    Yellow (6 stones, each 30 grams)
    Green (3 stones, each 20 grams)

    First batch (Yellow) goes to pits: 1, 3, 5, 7, 9, and 11. H=45.
    Second batch (Blue) goes to pits: 2 and 8. H=45.
    Third batch (Yellow) goes to pits: 2, 4, 6, 8, 10, and 12. H=70.
    Fourth batch (Green) goes to pits: 3, 7, and 11. H=70.
    In this exercise, heuristic actually finds the optimum, i.e., H=W=70 grams, observed in pits 2 and 8.

    And the question:
    Prove that the worst-case of the heuristic solution, H, is always less than 2W.
    In other words, W ≤ H ≤ 2W always holds. If you disagree, then try to generate a counter-example.

    I will give my work in the first comment, because the above text is already too long.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Jan 2009
    Posts
    94
    And here is my work (which is NOT complete!)

    Let's make several definitions and some analysis:
    w_i: weight of the i-th batch.
    f_i: frequency (or periodicity?) of the i-th batch. (for yellow batches f_i=2, for red f_i=3, and so on...)
    Suppose that B-th batch is the last one placed in the mancala that determined the heuristic value, H. (weigth= w_B and frequency= f_B). NOTE: this may be different than the last batch placed!

    w_1 \geq w_2 \geq ... \geq w_B is always true due to sorting. (Step 1 of the heuristic)

    Now, suppose that the the first stone of the last batch is inserted in pit j. ( j is an integer between 1 and f_B). Because it must be placed in one of the first f_B pits.

    Then, the following pits will receive the last batch: j, j+f_B, j+2f_B, \ldots, j+12-f_B.

    Total: 12/f_B pits will receive the last batch.

    One more definition: Let T_j be the total weight of stones in pit j "before" the last batch is placed.

    T_k = \max\{T_j, T_{j+f_B}, T_{j+2f_B}, \ldots, T_{j+12-f_B}\}

    Now the heuristic value H = T_k + w_B.

    When the last batch is placed, there must be at least f_B many T_k's in the mancala. <-- this is important to see!

    Then here is a lower-bound for the optimum ( W):
    (f_B T_k / 12) + (w_B/f_B) \leq W
    \implies T_k + (w_B/f_B)(12/f_B) \leq W(12/f_B)
    \implies T_k + w_B \leq W(12/f_B)-(12w_B/(f_B)^2)+w_B
    left-hand side is the heuristic value:
    \implies H \leq (12/f_B)W + w_B ((f_B)^2 - 12)/(f_B)^2

    Another lower-boud on the optimum: W \geq w_B, So:
    \implies H \leq (12/f_B)W + W ((f_B)^2 - 12)/(f_B)^2
    \implies H \leq [(12/f_B) + ((f_B)^2 - 12)/(f_B)^2] W
    \implies H \leq [1 + (12(f_B-1)/(f_B)^2)] W

    Now if f_B=12 (last batch is purple),
    then H \leq (2 - 1/12) W

    So W \leq H \leq 2W holds. But this is true only if the last batch (that determines the heuristic value) is purple. There is no guarantee that "that last batch" will be purple.

    So the proof is not complete! But this may be a starting point. Now what?
    Thanks...
    Last edited by oswaldo; March 17th 2011 at 10:04 PM. Reason: Latex corrections
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Balanced Strings
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: August 20th 2011, 06:31 PM
  2. [SOLVED] Two balanced fair coins
    Posted in the Statistics Forum
    Replies: 2
    Last Post: March 15th 2011, 08:40 AM
  3. Balanced and absorbant sets
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: March 10th 2011, 12:06 AM
  4. balanced incomplete block designs
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2010, 01:48 PM
  5. Repeated Tossing of Balanced Die
    Posted in the Statistics Forum
    Replies: 3
    Last Post: November 8th 2009, 04:39 AM

Search Tags


/mathhelpforum @mathhelpforum