assignment problem in which boxes have different capacities












0












$begingroup$


Suppose that there are $M$ numbers, $a_1,cdots,a_M$, and $K$ boxes. For each box $k$, $k=1,cdots,K$, we can put $Q_k$ different numbers in it, in which each $Q_k$ is given and satisfies $1leq Q_k < M$. Now I want to put different numbers into different boxes. Let $mathcal{A}_m$ denote the set of boxes that has $a_m$, $m=1,cdots,M$. Correspondingly, we can define $mathcal{B}_k={m:kin mathcal{A}_m}$ as the set of numbers that box $k$ has, $k=1,cdots,K$.



There are many combinations to put different numbers into different boxes such that each number is in at least one box. But I want to find the best assignment strategy among all these combinations to solve the following problem



begin{align}
mathop{ underset{mathcal{A}_1,cdots,mathcal{A}_M,P}{min}} & ~ P \
mathrm{s.t.} & ~ Lambda_mneq emptyset, ~~~ m=1,cdots,M, \ & ~ |mathcal{B}_k| leq Q_k, ~~~ k=1,cdots,K, \ & ~ sumlimits_{knotin mathcal{A}_m}Q_k leq P, ~~~ m=1,cdots,M.
end{align}



In other words, if $a_m$ is not in box $k$, i.e., $knotin mathcal{A}_m$, we have a penalty of $Q_k$ for $a_m$, i.e., the capacity of box $k$. As a result, for any assignment strategy, the penalty for $a_m$ is $sum_{knotin mathcal{A}_m}Q_k$, $m=1,cdots,M$. We want to find one assignment strategy to minimize the maximum penalty among all the $M$ numbers.



In the special case of $Q_k=Q$, $forall k$, i.e., all the boxes have the identical capacity, the optimal assignment is simple, because we can assign the numbers equally in different boxes with identical $|mathcal{A}_m|$'s for all $m$. But I am not clear how to solve the above assignment problem in the general case with arbitrary values of $Q_k$'s.



Is there a closed form optimal value to the above problem, or is there any polynomial time algorithm to solve the above problem?



Thank you.






combinations







share|cite|improve this question









$endgroup$

















    0












    $begingroup$


    Suppose that there are $M$ numbers, $a_1,cdots,a_M$, and $K$ boxes. For each box $k$, $k=1,cdots,K$, we can put $Q_k$ different numbers in it, in which each $Q_k$ is given and satisfies $1leq Q_k < M$. Now I want to put different numbers into different boxes. Let $mathcal{A}_m$ denote the set of boxes that has $a_m$, $m=1,cdots,M$. Correspondingly, we can define $mathcal{B}_k={m:kin mathcal{A}_m}$ as the set of numbers that box $k$ has, $k=1,cdots,K$.



    There are many combinations to put different numbers into different boxes such that each number is in at least one box. But I want to find the best assignment strategy among all these combinations to solve the following problem



    begin{align}
    mathop{ underset{mathcal{A}_1,cdots,mathcal{A}_M,P}{min}} & ~ P \
    mathrm{s.t.} & ~ Lambda_mneq emptyset, ~~~ m=1,cdots,M, \ & ~ |mathcal{B}_k| leq Q_k, ~~~ k=1,cdots,K, \ & ~ sumlimits_{knotin mathcal{A}_m}Q_k leq P, ~~~ m=1,cdots,M.
    end{align}



    In other words, if $a_m$ is not in box $k$, i.e., $knotin mathcal{A}_m$, we have a penalty of $Q_k$ for $a_m$, i.e., the capacity of box $k$. As a result, for any assignment strategy, the penalty for $a_m$ is $sum_{knotin mathcal{A}_m}Q_k$, $m=1,cdots,M$. We want to find one assignment strategy to minimize the maximum penalty among all the $M$ numbers.



    In the special case of $Q_k=Q$, $forall k$, i.e., all the boxes have the identical capacity, the optimal assignment is simple, because we can assign the numbers equally in different boxes with identical $|mathcal{A}_m|$'s for all $m$. But I am not clear how to solve the above assignment problem in the general case with arbitrary values of $Q_k$'s.



    Is there a closed form optimal value to the above problem, or is there any polynomial time algorithm to solve the above problem?



    Thank you.






    combinations







    share|cite|improve this question









    $endgroup$















      0












      0








      0





      $begingroup$


      Suppose that there are $M$ numbers, $a_1,cdots,a_M$, and $K$ boxes. For each box $k$, $k=1,cdots,K$, we can put $Q_k$ different numbers in it, in which each $Q_k$ is given and satisfies $1leq Q_k < M$. Now I want to put different numbers into different boxes. Let $mathcal{A}_m$ denote the set of boxes that has $a_m$, $m=1,cdots,M$. Correspondingly, we can define $mathcal{B}_k={m:kin mathcal{A}_m}$ as the set of numbers that box $k$ has, $k=1,cdots,K$.



      There are many combinations to put different numbers into different boxes such that each number is in at least one box. But I want to find the best assignment strategy among all these combinations to solve the following problem



      begin{align}
      mathop{ underset{mathcal{A}_1,cdots,mathcal{A}_M,P}{min}} & ~ P \
      mathrm{s.t.} & ~ Lambda_mneq emptyset, ~~~ m=1,cdots,M, \ & ~ |mathcal{B}_k| leq Q_k, ~~~ k=1,cdots,K, \ & ~ sumlimits_{knotin mathcal{A}_m}Q_k leq P, ~~~ m=1,cdots,M.
      end{align}



      In other words, if $a_m$ is not in box $k$, i.e., $knotin mathcal{A}_m$, we have a penalty of $Q_k$ for $a_m$, i.e., the capacity of box $k$. As a result, for any assignment strategy, the penalty for $a_m$ is $sum_{knotin mathcal{A}_m}Q_k$, $m=1,cdots,M$. We want to find one assignment strategy to minimize the maximum penalty among all the $M$ numbers.



      In the special case of $Q_k=Q$, $forall k$, i.e., all the boxes have the identical capacity, the optimal assignment is simple, because we can assign the numbers equally in different boxes with identical $|mathcal{A}_m|$'s for all $m$. But I am not clear how to solve the above assignment problem in the general case with arbitrary values of $Q_k$'s.



      Is there a closed form optimal value to the above problem, or is there any polynomial time algorithm to solve the above problem?



      Thank you.






      combinations







      share|cite|improve this question









      $endgroup$




      Suppose that there are $M$ numbers, $a_1,cdots,a_M$, and $K$ boxes. For each box $k$, $k=1,cdots,K$, we can put $Q_k$ different numbers in it, in which each $Q_k$ is given and satisfies $1leq Q_k < M$. Now I want to put different numbers into different boxes. Let $mathcal{A}_m$ denote the set of boxes that has $a_m$, $m=1,cdots,M$. Correspondingly, we can define $mathcal{B}_k={m:kin mathcal{A}_m}$ as the set of numbers that box $k$ has, $k=1,cdots,K$.



      There are many combinations to put different numbers into different boxes such that each number is in at least one box. But I want to find the best assignment strategy among all these combinations to solve the following problem



      begin{align}
      mathop{ underset{mathcal{A}_1,cdots,mathcal{A}_M,P}{min}} & ~ P \
      mathrm{s.t.} & ~ Lambda_mneq emptyset, ~~~ m=1,cdots,M, \ & ~ |mathcal{B}_k| leq Q_k, ~~~ k=1,cdots,K, \ & ~ sumlimits_{knotin mathcal{A}_m}Q_k leq P, ~~~ m=1,cdots,M.
      end{align}



      In other words, if $a_m$ is not in box $k$, i.e., $knotin mathcal{A}_m$, we have a penalty of $Q_k$ for $a_m$, i.e., the capacity of box $k$. As a result, for any assignment strategy, the penalty for $a_m$ is $sum_{knotin mathcal{A}_m}Q_k$, $m=1,cdots,M$. We want to find one assignment strategy to minimize the maximum penalty among all the $M$ numbers.



      In the special case of $Q_k=Q$, $forall k$, i.e., all the boxes have the identical capacity, the optimal assignment is simple, because we can assign the numbers equally in different boxes with identical $|mathcal{A}_m|$'s for all $m$. But I am not clear how to solve the above assignment problem in the general case with arbitrary values of $Q_k$'s.



      Is there a closed form optimal value to the above problem, or is there any polynomial time algorithm to solve the above problem?



      Thank you.






      combinations




      combinations






      share|cite|improve this question













      share|cite|improve this question











      share|cite|improve this question




      share|cite|improve this question










      asked Dec 27 '18 at 4:24









      LiangLiang

      312




      312






















          1 Answer
          1






          active

          oldest

          votes


















          0












          $begingroup$

          For each box $k$, we have a penalty of $Q_k$ for each $A_m$ not in box $k$. To minimize the penalty we need to put as many numbers as possible into each box. If we put $Q_k$ numbers in the box, there will be $M-Q_k$ numbers not in the box, and we have a penalty of $Q_k(M-Q_k)$. This is independent of which numbers are in the box.



          Any distribution that has all boxes full will have minimum total penalty.






          share|cite|improve this answer









          $endgroup$













          • $begingroup$
            Hi, thanks for your comments. However, I am not trying to minimize the total penalty. For each $a_m$, it has an individual penalty $sum_{knotin A_m} Q_k$. I want to minimize the maximum of the individual penalty among $a_m$'s.
            $endgroup$
            – Liang
            Dec 30 '18 at 2:14











          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


















          StackExchange.ready(
          function () {
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3053588%2fassignment-problem-in-which-boxes-have-different-capacities%23new-answer', 'question_page');
          }
          );

          Post as a guest















          Required, but never shown

























          1 Answer
          1






          active

          oldest

          votes








          1 Answer
          1






          active

          oldest

          votes









          active

          oldest

          votes






          active

          oldest

          votes









          0












          $begingroup$

          For each box $k$, we have a penalty of $Q_k$ for each $A_m$ not in box $k$. To minimize the penalty we need to put as many numbers as possible into each box. If we put $Q_k$ numbers in the box, there will be $M-Q_k$ numbers not in the box, and we have a penalty of $Q_k(M-Q_k)$. This is independent of which numbers are in the box.



          Any distribution that has all boxes full will have minimum total penalty.






          share|cite|improve this answer









          $endgroup$













          • $begingroup$
            Hi, thanks for your comments. However, I am not trying to minimize the total penalty. For each $a_m$, it has an individual penalty $sum_{knotin A_m} Q_k$. I want to minimize the maximum of the individual penalty among $a_m$'s.
            $endgroup$
            – Liang
            Dec 30 '18 at 2:14
















          0












          $begingroup$

          For each box $k$, we have a penalty of $Q_k$ for each $A_m$ not in box $k$. To minimize the penalty we need to put as many numbers as possible into each box. If we put $Q_k$ numbers in the box, there will be $M-Q_k$ numbers not in the box, and we have a penalty of $Q_k(M-Q_k)$. This is independent of which numbers are in the box.



          Any distribution that has all boxes full will have minimum total penalty.






          share|cite|improve this answer









          $endgroup$













          • $begingroup$
            Hi, thanks for your comments. However, I am not trying to minimize the total penalty. For each $a_m$, it has an individual penalty $sum_{knotin A_m} Q_k$. I want to minimize the maximum of the individual penalty among $a_m$'s.
            $endgroup$
            – Liang
            Dec 30 '18 at 2:14














          0












          0








          0





          $begingroup$

          For each box $k$, we have a penalty of $Q_k$ for each $A_m$ not in box $k$. To minimize the penalty we need to put as many numbers as possible into each box. If we put $Q_k$ numbers in the box, there will be $M-Q_k$ numbers not in the box, and we have a penalty of $Q_k(M-Q_k)$. This is independent of which numbers are in the box.



          Any distribution that has all boxes full will have minimum total penalty.






          share|cite|improve this answer









          $endgroup$



          For each box $k$, we have a penalty of $Q_k$ for each $A_m$ not in box $k$. To minimize the penalty we need to put as many numbers as possible into each box. If we put $Q_k$ numbers in the box, there will be $M-Q_k$ numbers not in the box, and we have a penalty of $Q_k(M-Q_k)$. This is independent of which numbers are in the box.



          Any distribution that has all boxes full will have minimum total penalty.







          share|cite|improve this answer












          share|cite|improve this answer



          share|cite|improve this answer










          answered Dec 28 '18 at 14:12









          Daniel MathiasDaniel Mathias

          1,36018




          1,36018












          • $begingroup$
            Hi, thanks for your comments. However, I am not trying to minimize the total penalty. For each $a_m$, it has an individual penalty $sum_{knotin A_m} Q_k$. I want to minimize the maximum of the individual penalty among $a_m$'s.
            $endgroup$
            – Liang
            Dec 30 '18 at 2:14


















          • $begingroup$
            Hi, thanks for your comments. However, I am not trying to minimize the total penalty. For each $a_m$, it has an individual penalty $sum_{knotin A_m} Q_k$. I want to minimize the maximum of the individual penalty among $a_m$'s.
            $endgroup$
            – Liang
            Dec 30 '18 at 2:14
















          $begingroup$
          Hi, thanks for your comments. However, I am not trying to minimize the total penalty. For each $a_m$, it has an individual penalty $sum_{knotin A_m} Q_k$. I want to minimize the maximum of the individual penalty among $a_m$'s.
          $endgroup$
          – Liang
          Dec 30 '18 at 2:14




          $begingroup$
          Hi, thanks for your comments. However, I am not trying to minimize the total penalty. For each $a_m$, it has an individual penalty $sum_{knotin A_m} Q_k$. I want to minimize the maximum of the individual penalty among $a_m$'s.
          $endgroup$
          – Liang
          Dec 30 '18 at 2:14


















          draft saved

          draft discarded




















































          Thanks for contributing an answer to Mathematics Stack Exchange!


          • Please be sure to answer the question. Provide details and share your research!

          But avoid …



          • Asking for help, clarification, or responding to other answers.

          • Making statements based on opinion; back them up with references or personal experience.


          Use MathJax to format equations. MathJax reference.


          To learn more, see our tips on writing great answers.




          draft saved


          draft discarded














          StackExchange.ready(
          function () {
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3053588%2fassignment-problem-in-which-boxes-have-different-capacities%23new-answer', 'question_page');
          }
          );

          Post as a guest















          Required, but never shown





















































          Required, but never shown














          Required, but never shown












          Required, but never shown







          Required, but never shown

































          Required, but never shown














          Required, but never shown












          Required, but never shown







          Required, but never shown







          -

          Popular posts from this blog

          Index of /

          This page is only for reference, If you need detailed information, please check here
          Read more

          Tribalistas

          Image
            Nota: Para o álbum homônimo, veja Tribalistas (álbum de 2002). Para o segundo álbum homônimo, veja Tribalistas (álbum de 2017). Para o tipo de organização tribal, veja Tribalismo. Tribalistas Informação geral Origem Salvador e Rio de Janeiro País   Brasil Gênero(s) MPB Pop Samba Período em atividade 2002–2004 2017–atualmente Gravadora(s) EMI Phonomotor Records Universal Music Afiliação(ões) Dadi Pretinho da Serrinha Margareth Menezes Integrantes Arnaldo Antunes Carlinhos Brown Marisa Monte Página oficial www2.uol.com.br/tribalistas/ ...
          Read more

          Listed building

          Image
          Listed building (literalmente: prédio listado ) é toda estrutura protegida por lei pelo complexo sistema de tombamento do Reino Unido. Um listed building é qualquer estrutura oficialmente designada como tendo especial interesse arquitetônico, histórico ou cultural. É um estatuto amplamente usado, aplicado a centenas de milhares de estruturas. Estruturas tombadas não podem ser alteradas sem permissão especial, e desfrutam de isenções fiscais e outros benefícios. Cada um dos países do Reino Unido trata tombamento de forma diferente: Índice 1 Inglaterra 2 País de Gales 3 Irlanda do Norte 4 Escócia 5 Referências Inglaterra | O Palácio de Buckingham, Londres. As estruturas tombadas são listadas no Statutory List of Buildings of Special Architectural or Historic Interest , e incluem campos, sinais de trânsito, piers e áreas geográficas. A principal legislação pertinente é o Ancient Monuments and Archaeological Areas Act 1979 , [ 1 ] embora legisla...
          Read more