0
$\begingroup$

We all know that, given a matroid $(E, \mathcal{I})$, Edmonds' Matroid partitioning algorithm will result in a tuple of $E$-covering, pairwise-disjoint independent sets $(I_1, ..., I_k)$ with optimal (smallest) $k$.

Assume the sizes of $I_j$ are decreasingly sorted: $|I_1| \ge \; ... \; \ge |I_k|$.

My question: Is $(|I_1|, ..., |I_k|)$ optimal (largest) w.r.t the lexicographical order of the lexicon $\mathbb{Z^+} = \{ 1 < 2 < 3 < ... \}$.

If this is NOT the case, is there any algorithm finding a tuple of $E$-covering, pairwise-disjoint independent sets $(I_1, ..., I_k)$ with the optimality of $(|I_1|, ..., |I_k|)$ ? Potentially it may sacrifice the optimality of $k$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.