Questions tagged [matroids]
The matroids tag has no usage guidance.
16 questions
4
votes
1
answer
109
views
Trying to figure if greedy algorithm is a matroid (or greedoid)
I know that if I can express a problem as a (weighted) matroid M = (E, S) or a greedoid then I can assure that there is an algorithm which will give me the optimal solution. For example for matroids ...
- 126
0
votes
1
answer
40
views
Matroid Closure follows the Closure Operator Properties
I want to show that for a matroid $M=(E,\mathcal{I})$ the closure of $S\subseteq E$ i.e. $$cl(S)=\{x\in E\mid rank(S\cup\{x\})=rank(S)\}$$ actually follows the closure operator properties:
$\forall$ $...
- 145
1
vote
1
answer
242
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 ...
- 53
1
vote
0
answers
34
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:
...
- 457
4
votes
1
answer
1k
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-...
- 143
1
vote
0
answers
51
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 ...
3
votes
2
answers
341
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 ...
- 1,154
2
votes
1
answer
463
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 ...
- 119
2
votes
1
answer
214
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, ...
- 281
1
vote
1
answer
55
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 ...
- 267
6
votes
0
answers
170
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 ...
- 61
3
votes
0
answers
94
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 ...
4
votes
1
answer
725
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 ...
- 6,164
2
votes
1
answer
100
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 ...
- 22.8k
7
votes
1
answer
1k
views
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 ...
- 167
23
votes
1
answer
2k
views
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 ...
- 3,897