Matroid-constrained number partitioning is a variant of the

multiway number partitioning In computer science, multiway number partitioning is the problem of partitioning a multiset of numbers into a fixed number of subsets, such that the sums of the subsets are as similar as possible. It was first presented by Ronald Graham in 1969 in t ...

problem, in which the subsets in the partition should be independent sets of a

matroid In combinatorics, a branch of mathematics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being ...

. 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: * 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 In operations research, the makespan of a project is the length of time that elapses from the start of work to the end. This type of multi-mode resource constrained project scheduling problem (MRCPSP) seeks to create the shortest logical project sc ...

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 matroid In mathematics, the free matroid over a given ground-set ''E'' is the matroid in which the independent sets are all subsets of ''E''. It is a special case of a uniform matroid In mathematics, a uniform matroid is a matroid in which the independ ...

s (no constraints) and the ''m'' weight-functions are identical corresponds to

identical-machines scheduling Identical-machines scheduling is an optimization problem in computer science and operations research. We are given ''n'' jobs ''J''1, ''J''2, ..., ''Jn'' of varying processing times, which need to be scheduled on ''m'' identical machines, such that ...

, also known as

. The case of free matroids and different weight-functions corresponds to

unrelated-machines scheduling Unrelated-machines scheduling is an optimization problem in computer science and operations research. It is a variant of optimal job scheduling. We need to schedule ''n'' jobs ''J''1, ''J''2, ..., ''Jn'' on ''m'' different machines, such that a cert ...

. **The special case of

uniform matroid In mathematics, a uniform matroid is a matroid in which the independent sets are exactly the sets containing at most ''r'' elements, for some fixed integer ''r''. An alternative definition is that every permutation of the elements is a symmetry. ...

s corresponds to cardinality constraints on the subsets. The more general case of

partition matroid In mathematics, a partition matroid or partitional matroid is a matroid that is a direct sum of uniform matroids. It is defined over a base set in which the elements are partitioned into different categories. For each category, there is a ''capaci ...

s 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 In combinatorial optimization, the matroid intersection problem is to find a largest common independent set in two matroids over the same ground set. If the elements of the matroid are assigned real weights, the weighted matroid intersection proble ...

problem'' - finding a maximum-weight subset that is simultaneously independent in two given matroids. 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 matroid In the mathematical theory of matroids, a graphic matroid (also called a cycle matroid or polygon matroid) is a matroid whose independent sets are the forests in a given finite undirected graph. The dual matroids of graphic matroids are called co- ...

s can be used to solve the minimum bottleneck spanning tree problem. *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. *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''.

General matroid constraints

General matroid constraints were first considered by Burkard and Yao. They showed that minimizing (sum,max) can be done in polynomial time by a

greedy algorithm A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage. In many problems, a greedy strategy does not produce an optimal solution, but a greedy heuristic can yield locally ...

for a subclass of matroids, which includes

s. Hwang and Rothblum presented an alternative sufficient condition. Wu and Yao presented an approximation algorithm for minimizing (max,sum) with general matroid constraints. Abbassi, Mirrokni and Thakur present an approximation algorithm for a problem of ''diversity maximization'' under matroid constraints. Kawase, Kimura, Makino and Sumita 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 Matroid partitioning is a problem arising in the mathematical study of matroids and in the design and analysis of algorithms. Its goal is to partition the elements of a matroid into as few independent sets as possible. An example is the problem of ...

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

, which is polynomial.

References

{{Reflist Matroid theory Number partitioning

Special cases

General matroid constraints

Related problems

References