Questions tagged [matroids]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
23 votes
1 answer

How fundamental are matroids and greedoids in algorithm design?

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 ...
Nicholas Mancuso's user avatar
7 votes
1 answer

Greedy choice and matroids (greedoids)

As I was going through the material about the greedy approach, I came to know that a knowledge on matroids (greedoids) will help me approaching the problem properly. After reading about matroids I ...
Imposter's user avatar
  • 167
6 votes
0 answers

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 ...
ChubbyRuby's user avatar
4 votes
1 answer

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-...
vvaltchev's user avatar
  • 143
4 votes
1 answer

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 ...
Erel Segal-Halevi's user avatar
3 votes
2 answers

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 ...
Abhishek Ghosh's user avatar
3 votes
0 answers

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 ...
Matej Konecny's user avatar
2 votes
1 answer

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 ...
Juho's user avatar
  • 22.6k
2 votes
1 answer

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, ...
Chill2Macht's user avatar
2 votes
1 answer

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 ...
Shakil Ahamed's user avatar
1 vote
1 answer

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 ...
Ash Ketchum's user avatar
1 vote
1 answer

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 ...
Belgi's user avatar
  • 267
1 vote
0 answers

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: ...
3nondatur's user avatar
  • 457
1 vote
0 answers

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 ...
Novice_researcher's user avatar