𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On Greedy Bases Packing in Matroids

✍ Scribed by Brahim Chaourar

Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
169 KB
Volume
23
Category
Article
ISSN
0195-6698

No coin nor oath required. For personal study only.

✦ Synopsis

Let S be a finite set and M = (S, B) be a matroid where B is the set of its bases. We say that a basis B is greedy in M or the pair (M, B) is greedy if, for every sum of bases vector w, the coefficient:

where B and its characteristic vector will not be distinguished, is integer. We define a notion of minors for (M, B) pairs and we give a characterization of greedy pairs by excluded minors. This characterization gives a large class of matroids for which an integer CarathΓ©odory's theorem is true.

πŸ“œ SIMILAR VOLUMES

Bases in oriented matroids
Bases in oriented matroids
✍ Michel Las Vergnas πŸ“‚ Article πŸ“… 1978 πŸ› Elsevier Science 🌐 English βš– 366 KB
Random packing by matroid bases and tria
Random packing by matroid bases and triangles
✍ Safwan Akkari πŸ“‚ Article πŸ“… 1995 πŸ› Elsevier Science 🌐 English βš– 356 KB

Let M be a matroid on a finite set E(M). Then M is packable by bases if E(M) is the disjoint union of bases. A partial packing of M is a collection of disjoint bases whose union is a proper subset of E(M). M is a randomly packable by bases if every partial packing can be extended to a packing of M.