# Questions tagged [matroids]

The tag has no usage guidance.

10 questions
Filter by
Sorted by
Tagged with
219 views

### Difficulty in understanding the proof of the lemma : “Matroids exhibit the optimal-substructure property”

I was going through the text "Introduction to Algorithms" by Cormen et. al. where I came across a lemma in which I could not understand a vital step in the proof. Before going into the lemma ...
167 views

### Activity Selection and Matroid Theory

Many people on different articles suggests that if an optimization problem has a greedy solution, the underlying structure must have matroid property. I was trying to understand this. So far, I was ...
110 views

### Can LP for matroid polytopes be solved using the greedy algorithm?

For general linear programming (LP), i.e. optimization of a linear objective over a general polyhedron, to the best of my knowledge/recollection one can use the simplex algorithm (or hypothetically, ...
41 views

### A $log(k)$ algorithm for the matroid secretary problem

I'm reading the following article that presents a $log(k)$ algorithm for your secretary problem. I'm in the analysis section at the left part of page 5 there is the following claim: $B^*$ is a ...
151 views

### When does greediness guarantee optimality?

I was wondering if there is any theoretical results characterizing under what condition does greedy algorithm actually finds the optimal solution. Here is a motivating example. Suppose you are trying ...
88 views

### Is the intersection of $k \geq 3$ graphic matroids in P? [closed]

It is known that intersection of three general matroids is NP-hard (wiki), which is done via reduction from Hamiltonian cycle. The reduction uses one graphic matroid and two connectivity matroids. A ...
392 views

### Finding a maximum-weight base of a a matroid, in reverse

Given a weighted matroid with positive weights, we can find a independent set with a maximum weight with a greedy algorithm: Start with an empty set (by definition of matroid, it is independent). Add ...
93 views

### What is a good resource to learn about oriented matroids in the context of digraphs and optimization?

I am interested in oriented matroids in the context of directed graphs and optimization. Unfortunately, I know very little of the topic. Is there a book, article or a resource that serves as a good ...
Initially, matroids were introduced to generalize the notions of linear independence of a collection of subsets $E$ over some ground set $I$. Certain problems that contain this structure permit greedy ...