Matroid-constrained number partitioning

<h2 id="special-cases">Special cases</h2>
Some important special cases of matroid-constrainted partitioning problems are:<a class="footnote-ref" id="fnref:1" href="#fn:1">1</a>

<ul><li>The (max,sum) objective is the maximum over all subsets, of the total weight in the subset. When the items represent jobs and the weights represent their length, this objective is simply the <a href="/facts/Makespan/w1HEjJaQ">makespan</a> of the schedule. Therefore, minimizing this objective is equivalent to minimizing the makespan under matroid constraints. The dual goal of maximizing (min,sum) has also been studied in this context.
<ul><li>The special case in which the matroids are <a href="/facts/Free_matroid/lhwaDBUk">free matroids</a> (no constraints) and the m weight-functions are identical corresponds to <a href="/facts/Identical-machines_scheduling/lwNSXMs6">identical-machines scheduling</a>, also known as <a href="/facts/Multiway_number_partitioning/6dUsX2HI">multiway number partitioning</a>. The case of free matroids and different weight-functions corresponds to <a href="/facts/Unrelated-machines_scheduling/V3cIylxs">unrelated-machines scheduling</a>.</li>
<li>The special case of <a href="/facts/Uniform_matroid/nVAV66la">uniform matroids</a> corresponds to cardinality constraints on the subsets. The more general case of <a href="/facts/Partition_matroid/cNFyr6V1">partition matroids</a> corresponds to categorized cardinality constraints. These problems are described in the page on <a href="/facts/Balanced_number_partitioning/zWSTmzc5">balanced number partitioning</a>.</li></ul></li>
<li>The (sum,sum) objective is the sum of weights of all items in all subsets, where the weights in each subset i are computed by the weight-function of matroid i. Minimizing this objective can be reduced to the weighted <a href="/facts/Matroid_intersection/y3D6RmaD">matroid intersection</a> problem - finding a maximum-weight subset that is simultaneously independent in two given matroids. This problem is solvable in polynomial time.</li>
<li>The (max,max) objective is the maximum weight in all subsets, where the weights in each subset i are computed by the weight-function of matroid i. Minimizing this objective with <a href="/facts/Graphic_matroid/UkEwWWhl">graphic matroids</a> can be used to solve the <a href="/facts/Minimum_bottleneck_spanning_tree/udJPfNX8">minimum bottleneck spanning tree</a> problem.</li>
<li>The (sum,min) objective is the sum of minimum weights in all subsets. Maximizing this objective, with k identical <a href="/facts/Graphical_matroid/UkEwWWhl">graphical matroids</a>, can be used to solve the maximum total capacity <a href="/facts/Spanning_tree/qQPN9taR">spanning tree partition</a> problem.</li>
<li>The (sum,max) objective is the sum of maximum weights in all subsets. This objective can represent the total memory needed for scheduling, when each matroid i represents the feasible allocations in machine i.</li></ul>
<h2 id="general-matroid-constraints">General matroid constraints</h2>
General matroid constraints were first considered by Burkard and Yao.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a> They showed that minimizing (sum,max) can be done in polynomial time by a <a href="/facts/Greedy_algorithm/alfsekco">greedy algorithm</a> for a subclass of matroids, which includes <a href="/facts/Partition_matroid/cNFyr6V1">partition matroids</a>. Hwang and Rothblum<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a> presented an alternative sufficient condition.
Wu and Yao<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a> presented an approximation algorithm for minimizing (max,sum) with general matroid constraints.
Abbassi, Mirrokni and Thakur<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a> present an approximation algorithm for a problem of diversity maximization under matroid constraints.
Kawase, Kimura, Makino and Sumita<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a> show that the maximization problems can be reduced to minimization problems. Then, they analyze seven minimization problems:

<ul><li>Minimizing (sum,max): the problem is strongly NP-hard even when the matroids and weights are identical. There is a PTAS for identical matroids and weights. For general matroids and weights, there is an εm-approximation algorithm for any ε > 0. It is NP-hard to approximate with factor O(log m).</li>
<li>Minimizing (min,min), (max,max), (min,max) and (min,sum): there are polynomial-time algorithms. They reduce the problems to the feasibility problem of the <a href="/facts/Matroid_partitioning/GyyRPGfj">matroid partitioning</a> problem.</li>
<li>Minimizing (max,min) and (sum,min): there are polynomial-time algorithms for identical matroids and weights. In the general case, it is strongly NP-hard even to approximate.</li>
<li>The other two problems were analyzed in previous works: minimizing (max,sum) is known to be strongly NP-hard (<a href="/facts/3-partition_problem/X4uW5f57">3-partition</a> is a special case), and minimizing (sum,sum) can be reduced to weighted <a href="/facts/Matroid_intersection/y3D6RmaD">matroid intersection</a>, which is polynomial.</li></ul>
<h2 id="related-problems">Related problems</h2>
<a href="/facts/Matroid_partitioning/GyyRPGfj">Matroid partitioning</a> is a different problem, in which the number of parts m is not fixed. There is a single matroid, and the goal is to partition its elements into a smallest number of independent sets.

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Kawase, Yasushi; Kimura, Kei; Makino, Kazuhisa; Sumita, Hanna (2021-02-15). "Optimal Matroid Partitioning Problems". Algorithmica. 83 (6): 1653–1676. arXiv:1710.00950. doi:10.1007/s00453-021-00797-9. ISSN 0178-4617. S2CID 233888432. <a href="https://link-springer-com.mgs.ariel.ac.il/article/10.1007/s00453-021-00797-9" target="_blank">https://link-springer-com.mgs.ariel.ac.il/article/10.1007/s00453-021-00797-9</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Burkard, Rainer E.; Yao, En-Yu (1990-07-01). "Constrained partitioning problems". Discrete Applied Mathematics. 28 (1): 21–34. doi:10.1016/0166-218X(90)90091-P. ISSN 0166-218X. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Hwang, Frank K.; Rothblum, Uriel G. (1994-04-20). "Constrained partitioning problems". Discrete Applied Mathematics. 50 (1): 93–96. doi:10.1016/0166-218X(94)90166-X. ISSN 0166-218X. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Wu, Biao; Yao, En-yu (2008-10-01). "Min-max partitioning problem with matroid constraint". Journal of Zhejiang University Science A. 9 (10): 1446–1450. Bibcode:2008JZUSA...9.1446W. doi:10.1631/jzus.A071606. ISSN 1862-1775. S2CID 119998340. <a href="https://doi.org/10.1631/jzus.A071606" target="_blank">https://doi.org/10.1631/jzus.A071606</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Abbassi, Zeinab; Mirrokni, Vahab S.; Thakur, Mayur (2013-08-11). "Diversity maximization under matroid constraints". Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining. KDD '13. New York, NY, USA: Association for Computing Machinery. pp. 32–40. doi:10.1145/2487575.2487636. ISBN 978-1-4503-2174-7. S2CID 10844235. <a href="978-1-4503-2174-7" target="_blank">978-1-4503-2174-7</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Kawase, Yasushi; Kimura, Kei; Makino, Kazuhisa; Sumita, Hanna (2021-02-15). "Optimal Matroid Partitioning Problems". Algorithmica. 83 (6): 1653–1676. arXiv:1710.00950. doi:10.1007/s00453-021-00797-9. ISSN 0178-4617. S2CID 233888432. <a href="https://link-springer-com.mgs.ariel.ac.il/article/10.1007/s00453-021-00797-9" target="_blank">https://link-springer-com.mgs.ariel.ac.il/article/10.1007/s00453-021-00797-9</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
</ol>

Matroid-constrained number partitioning open-in-new

Matroid-constrained number partitioning