# Questions tagged [matroids]

The tag has no usage guidance.

15 questions
Filter by
Sorted by
Tagged with
47 views

### Recursively deleting spanning forest from graph, how many iterations maximum to get to the empty graph?

As in the question stated, I am interested in the approximation factor of the greedy approach to compute the arboricity of the graph. My intuition tells me the factor should not be bigger than $2$, ...
1 vote
67 views

### Rank of a graph in matroid theory

I was going through the concept of graphs as matroids and I came upon the rank of a graph. Wikipedia lists it as $n - c$, $n = |V|$, $c =$ # of connected components. I do understand rank and nullity ...
1 vote
29 views

### The Greedy Algorihm for Matroids works for maximisation and minimisation

I am working on the following exercise: Let $(S,\mathcal{F})$ be a matroid and let $c:S \rightarrow \mathbb{R}$ be a weight function on $S$. Find an algorithm that solves the following problem: ...
687 views

### A task-scheduling problem as a matroid (CLRS book)

I don't understand very well section 16.5 of the 3rd edition of the famous Introduction to Algorithms book, known as CLRS. It defines the problem of scheduling unit-...
1 vote
43 views

### Does the existence of a matroid structure imply that the greedy algorithm is optimal?

I was going through the topic of matroid structures for the problems like Activity selection ,minimum spanning tree. I also came to know how to solve if a problem exhibits matroid structure. The ...
307 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 ...
356 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 ...
173 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, ...
1 vote
47 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 ...
164 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 ...
621 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 ...
92 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 ...
99 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 ...