Matroid-constrained number partitioning
Matroid-constrained number partitioning is a variant of the multiway number partitioning problem, in which the subsets in the partition should be independent sets of a matroid. The input to this problem is a set S of items, a positive integer m, and some m matroids over the same set S. The goal is to partition S into m subsets, such that each subset i is an independent set in matroid i. Subject to this constraint, some objective function should be minimized, for example, minimizing the largest sum item sizes in a subset. In a more general variant, each of the m matroids has a weight function, which assigns a weight to each element of the ground-set. Various objective functions have been considered. For each of the three operators max,min,sum, one can use this operator on the weights of items in each subset, and on the subsets themselves. All in all, there are 9 possible objective functions, each of which can be maximized or minimized.
Special cases
Some important special cases of matroid-constrainted partitioning problems are:[1]
- 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 makespan 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.
- The special case in which the matroids are free matroids (no constraints) and the m weight-functions are identical corresponds to identical-machines scheduling, also known as multiway number partitioning. The case of free matroids and different weight-functions corresponds to unrelated-machines scheduling.
- The special case of uniform matroids corresponds to cardinality constraints on the subsets. The more general case of partition matroids corresponds to categorized cardinality constraints. These problems are described in the page on balanced number partitioning.
- 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 matroid intersection problem - finding a maximum-weight subset that is simultaneously independent in two given matroids.[clarification needed] This problem is solvable in polynomial time.
- 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 graphic matroids can be used to solve the minimum bottleneck spanning tree problem.[clarification needed]
- The (sum,min) objective is the sum of minimum weights in all subsets. Maximizing this objective, with k identical graphical matroids, can be used to solve the maximum total capacity spanning tree partition problem.[clarification needed]
- The (sum,max) objective is the sum of maximum weights in all subsets. This objective can represent the total memory needed for scheduling,[clarification needed] when each matroid i represents the feasible allocations in machine i.
General matroid constraints
General matroid constraints were first considered by Burkard and Yao.[2] They showed that minimizing (sum,max) can be done in polynomial time by a greedy algorithm for a subclass of matroids, which includes partition matroids. Hwang and Rothblum[3] presented an alternative sufficient condition.
Wu and Yao[4] presented an approximation algorithm for minimizing (max,sum) with general matroid constraints.
Abbassi, Mirrokni and Thakur[5] present an approximation algorithm for a problem of diversity maximization under matroid constraints.
Kawase, Kimura, Makino and Sumita[1] show that the maximization problems can be reduced to minimization problems. Then, they analyze seven minimization problems:
- 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).
- 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 matroid partitioning problem.
- 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.
- The other two problems were analyzed in previous works: minimizing (max,sum) is known to be strongly NP-hard (3-partition is a special case), and minimizing (sum,sum) can be reduced to weighted matroid intersection, which is polynomial.
Related problems
Matroid partitioning 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.
References
- ↑ 1.0 1.1 Kawase, Yasushi; Kimura, Kei; Makino, Kazuhisa; Sumita, Hanna (2021-02-15). "Optimal Matroid Partitioning Problems". Algorithmica 83 (6): 1653–1676. doi:10.1007/s00453-021-00797-9. ISSN 0178-4617. https://link-springer-com.mgs.ariel.ac.il/article/10.1007/s00453-021-00797-9.
- ↑ Burkard, Rainer E.; Yao, En-Yu (1990-07-01). "Constrained partitioning problems" (in en). Discrete Applied Mathematics 28 (1): 21–34. doi:10.1016/0166-218X(90)90091-P. ISSN 0166-218X.
- ↑ Hwang, Frank K.; Rothblum, Uriel G. (1994-04-20). "Constrained partitioning problems" (in en). Discrete Applied Mathematics 50 (1): 93–96. doi:10.1016/0166-218X(94)90166-X. ISSN 0166-218X.
- ↑ Wu, Biao; Yao, En-yu (2008-10-01). "Min-max partitioning problem with matroid constraint" (in en). Journal of Zhejiang University Science A 9 (10): 1446–1450. doi:10.1631/jzus.A071606. ISSN 1862-1775. https://doi.org/10.1631/jzus.A071606.
- ↑ 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. https://doi.org/10.1145/2487575.2487636.
 |  |
