4
$\begingroup$

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 it goes something like:

T = {} sort(E) increasingly for e in the sorted array if (T union {e}) is an independent set T = T union {e}

which gives the minimum solution in $O(n\log(n) + nf(n))$ running time where $f$ is the time that takes to evaluate if its an independent set.

So for example I have the following problem: Given an array $E$ give the maximum value attainable summing up to $k$ elements of it. We can write it as the following matroid:

$ M = (E, S = \{ F \,\lvert\, \#F \leq k \land F \in \mathcal{P}(E) \}) $

It's easy to see that $S$ is an independent set because it follows all the axioms of a matroid:

  1. $\emptyset \in S$.
  2. If $A \in S$ and $B \subseteq A$ then $B \in S$.
  3. If $A, B \in S$ and $\lvert A \rvert > \lvert B \rvert$ then there is an $x \in A - B$ such that $B \cup \{x\} \in S$.

In this particular case our set weight function is $w(F) = \sum_{x \in F} \max(E) - x$. (because our first algorithm is a minimisation)

My problem then comes with a similar problem where we have a car that is travelling through a straight line and it can travel $L$ distance before refuelling, it also has mapped several points where it knows it can refuel, $x_1 \leq x_2 \cdots \leq x_n$.

We want to get the minimum number of stops needed for refuelling that gets us to $x_n$. The greedy strategy here is to move the car as much as possible before stopping each time. But I can't find any formulation to make this a matroid or greedoid.

For example I tried taking sets where all the points follow each other in the original line and they diff between min and max is less than L but that breaks the third axiom.

tl;dr I want to cast the last 3 paragraphs as a matroid but I'm having issues finding the independent set.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
+50
$\begingroup$

This might not qualify as a full answer but here is a reason why a naïve approach does not work to model this as a matroid.

Let $E = \{e_1, \ldots, e_n\}$ be your set of gas stations. Your assumption ($*$) says that for all $i < n$, there is a $j > i$ such that the distance $d(e_i, e_j) \leq L$, where $L$ is your maximum reach after refilling.

Let us call an ordered set $R = \{e_{i_1}, \ldots, e_{i_\ell}\} \subseteq E$ a roadmap if $d(e_{i_j}, e_{i_{j+1}}) \leq L$ for all $1 \leq j < \ell$ and $i_\ell = n$.

It is clear that the set of roadmaps does not satisfy the independec axioms of matroids as it is in general not downward-closed. But how about the complements? This gives us an independence system: $$\mathcal{I} = \{I \subseteq E \mid E \setminus I \text{ is a roadmap}\}.$$ Intuitively, a set of gas stations is independent if it is safe to pass all of these gas stations and you only fill up at gas stations in the complement.
Then $(1)$. $\varnothing \in \mathcal{I}$ is true by ($*$) and $(2)$ $I \subseteq I' \in \mathcal{I} \implies I \in \mathcal{I}$ holds as you only have more gas stations available when going from roadmap $E \setminus I'$ to roadmap $E \setminus I$. However, $(3)$ for all $I, I' \in \mathcal{I}$ with $|I| < |I'|$ there exists $e \in I' \setminus I$ such that $I+e \in \mathcal{I}$ is in general not true.

Consider the following example: The road is on the interval $[0, 15]$, maximum travel distance is $L = 5$ and we have gas stations $E = \{3, 5, 8, 10, 13, 15\}$. There is an optimal roadmap $\{5, 10, 15\}$ corresponding to the independent set $I' = \{3, 8, 13\}$. Another roadmap is $\{3, 8, 13, 15\}$ with independet set $I = \{5, 10\}$. Now it is easy to verify that $I$ and $I'$ do not satisfy $(3)$.

As additional remark (because I do not know how the question whether your setting can be modeled as matroid arised): The greedy algorithm that you proposed clearly finds an optimal solution (a simple exchange argument should prove this). Does this mean there has to be a matroid hidden somewhere?
The answer to this is no. For this to be true, the greedy algorithm has to fit the matroid greedy algorithm (as described by you in the upper half of the question). This includes that the matroid greedy always has to find a base no matter what order you choose for the elements. The greedy algorithm for the gas station problem on the other hand has to look at the items in order of their appearance on the road (actually with a look-ahead).

Improve this answer
$\endgroup$
4
  • $\begingroup$ The question arised from a problem set of greedy algorithms I have and my recent learning of matroids/greedoids, I wanted to see which ones could be cast as a matroid. So far I had little success. $\endgroup$ Commented Jul 30, 2024 at 17:27
  • $\begingroup$ Just to be sure I understand your argument, you're using the duality of matroids to show the complement is not a matroid and thus the original is also not a matroid? Is this enough or could there be more independent sets that allow it to be modelled as a matroid? (which I'm guessing is a really hard question) $\endgroup$ Commented Jul 30, 2024 at 17:29
  • $\begingroup$ Matroid duality was not really I what I was going for but sou can make that argument yes. In a sense, I showed that the set of inclusion-wise maximal sets of gas stations do not form a matroid base (in the example above, you see that they do not have the same cardinality). From there it follows that the set of minimal sets of gas station that give you a roadmap cannot be a matroid base set either by duality. $\endgroup$ Commented Jul 31, 2024 at 8:52
  • $\begingroup$ From there I think it is pretty much unambiguous that if you want the gas stations as your ground set of the matroid and bases should refer to optimal solutions, then you cannot do this with a matroid. If you find another way to model this, I would not completely exclude the possibility that there is a matroid somewhere but the intuition behind the model probably gets lost. $\endgroup$ Commented Jul 31, 2024 at 8:55

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.