mathematics

Matroid-constrained number partitioning

Matroid-constrained number partitioning is a mathematics topic covered in the lgStudy science library. This page brings together a partial reference excerpt, illustrations, worked examples, real-world applications and a short study plan, so you can understand Matroid-constrained number partitioning rather than just read about it. In short: 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.

Key takeaways

Matroid-constrained number partitioning belongs to mathematics; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Matroid-constrained number partitioning to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Matroid-constrained number partitioning from memory before moving on to harder problems.

Reference excerpt

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:

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. 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. 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 for a subclass of matroids, which includes partition matroids. 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 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

Worked examples

Example 1 — a first encounter with Matroid-constrained number partitioning

Start with the simplest possible case. Write down what Matroid-constrained number partitioning claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In mathematics, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Matroid-constrained number partitioning before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Matroid-constrained number partitioning ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Matroid-constrained number partitioning

In research: Matroid-constrained number partitioning appears in mathematics research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Matroid-constrained number partitioning in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Matroid-constrained number partitioning is common in secondary-school and first-year university syllabi. It links to neighbouring topics Matroid theory, Number partitioning, so understanding it makes those chapters shorter.
In everyday life: Look for Matroid-constrained number partitioning outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

Affiliate

Preply — study more efficiently by working with a personal tutor. 50% off.

How to study Matroid-constrained number partitioning in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Matroid-constrained number partitioning means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Matroid-constrained number partitioning out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Matroid-constrained number partitioning in simple terms?

Why does Matroid-constrained number partitioning matter?

Because it connects several mathematics ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Matroid-constrained number partitioning?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Matroid-constrained number partitioning.