nor's blog

By nor, 2 years ago, In English
  • Vote: I like it
  • +349
  • Vote: I do not like it

»
23 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Good article. However, learning matroid didn't give me any power solving greedy tasks :(

»
23 months ago, # |
  Vote: I like it +27 Vote: I do not like it

»
23 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Thanks for helping the community!

»
23 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Really helpful, thanks for the blog!!

»
23 months ago, # |
  Vote: I like it +8 Vote: I do not like it

another nor sir blog to star :prayge:

»
23 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Soon top 10 contributors :prayge:

»
16 months ago, # |
Rev. 3   Vote: I like it +11 Vote: I do not like it

nor I don't understand the second claim of the proof of theorem 1 part 1, mind clarifying?

  • Does the subsequence need to be contiguous?
  • As I understand the claim, if $$$t_1,t_2,a\in S$$$ and $$$t_1t_2,a\in L$$$, then $$$at_1\in L$$$. But this seems false for $$$L=\{\emptyset,a,at_2,t_1,t_1t_2\}$$$?
  • »
    »
    16 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Also, should Theorem 3 have $$$w:2^S\to\mathbb R$$$? That is, $$$w$$$ maps subsets of $$$S$$$ to reals.

    • »
      »
      »
      16 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Indeed, thanks for catching the typo.

  • »
    »
    16 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Seems like I messed up the claim while writing up the sketch.

    • Instead of us being able to pick an arbitrary subsequence, there simply exists a subsequence such that $$$st' \in L$$$.
    • No, it doesn't need to be contiguous. For example, if $$$s = pqr$$$, and $$$t = uvwxyz$$$, then a subsequence that works can be the subsequence $$$uxz$$$, so that the word $$$st'$$$ in the claim is $$$pqravwuyx$$$.
    • »
      »
      »
      16 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The second claim makes sense now, but I don't get third claim. Is it really a continuation of the first claim? Why would $$$sa\in L$$$ imply $$$st'\in L$$$? Isn't the latter string longer?

      • »
        »
        »
        »
        16 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        The part that it is a continuation is an error from when I mentioned the first claim elsewhere in the first draft, and the second claim was the first claim back then. It is also very poorly phrased in retrospect (in quite a lot of ways); it is actually connected to the subsequence $$$t'$$$ in the second claim. Here's what I meant when I wrote that (paraphrasing from my notes):

        Let's say we have $$$st, sa \in L$$$. Consider the $$$t'$$$ from the second claim, and the positions of the subsequence that was shifted by 1. If we move $$$a$$$ in that subsequence while preserving the order of the other elements, then the resulting $$$t"$$$ will satisfy $$$st" \in L$$$. (Looking at it in another way, we are shifting one part of the remaining subsequence to before $$$a$$$, while keeping the order of the remaining elements the same, which is essentially what the claim says).

        If we consider the previous example, where $$$s = pqr$$$, $$$t = uvwxyz$$$ and $$$t' = avwuyx$$$, we can move around the sequence $$$a$$$ within the characters $$$a, u, x$$$, while preserving the relative position of $$$u$$$ and $$$x$$$, any number of times to get $$$t"$$$ such that $$$st"$$$ is in $$$L$$$. Thus $$$t"$$$ can be $$$uvwayx$$$, $$$uvwxya$$$ and of course $$$t'$$$.

»
16 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

nor Regarding local forest greedoids:

One property of this structure is that for every element ...

Wouldn't $$$\{x\}$$$ be such a set? Why is this set unique (and what path does it induce)?

Never mind, I confused these with matroids.

  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Actually, I'm still confused about this property. There doesn't seem to be a unique set for the directed branching greedoid, is there?

    • »
      »
      »
      16 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Now I'm not sure how this issue can be resolved either. Looking through my references, I was referring to this and this for directed branching greedoids in the context of local forest greedoids, and the first link gives the claim for branching greedoids.

      Also, I just noticed there are other definitions of directed branching greedoids, so I probably inadvertently mixed them up — for instance, this paper gives the definition that I used in the examples above. For the purposes of proving the correctness of certain greedy algorithms on rooted graphs, however, the two definitions "should" both lead to correct proofs.

»
16 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Then the original definition of a greedoid and this definition of a set variant are equivalent, ...

Is it true that for any $$$L$$$ there is a corresponding $$$F$$$? If not, it doesn't seem correct to refer to these definitions as equivalent.

  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, this is true.

    • »
      »
      »
      16 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How do you show that this is true?

      • »
        »
        »
        »
        16 months ago, # ^ |
        Rev. 6   Vote: I like it 0 Vote: I do not like it

        Simply map a $$$w \in L$$$ to the set of its characters, call this mapping $$$f$$$. We claim that $$$f$$$ is the required mapping to go from $$$L$$$ to $$$F$$$. $$$|s| > |t|$$$ in $$$L$$$ implies, since $$$L$$$ is a simple language, that $$$f(s) \setminus f(t)$$$ is the set of characters that are in $$$s$$$ but not in $$$t$$$, and there can be at most one occurrence of any character in $$$S$$$ in the list of characters in $$$s$$$ but not in $$$t$$$ (with multiplicity). So for every $$$tx$$$ for $$$x \in s$$$ and $$$x \not \in t$$$, we have a unique element $$$f(t) \cup \{x\}$$$ in $$$F$$$. Now for any $$$A, B$$$ in $$$F$$$ with $$$|A| > |B|$$$, we can use any preimage of $$$A$$$ and any preimage of $$$B$$$ in $$$L$$$ to be able to claim that there is a $$$x$$$ in $$$A \setminus B$$$ such that $$$A \cup \{x\} \in F$$$. Abuse of notation: we will also denote the map from $$$L$$$ to the set of sets as $$$f$$$.

        For the other direction, considered an unordered greedoid $$$(S, F)$$$, and the maximal simple hereditary language $$$L$$$ such that $$$f(L) \subseteq F$$$. It is easy to check that $$$L$$$ is an ordered greedoid. Let's call this mapping $$$g$$$.

        Note that $$$f$$$ and $$$g$$$ applied in this order will map $$$L$$$ to itself — this can be shown by induction on word size.

        Since this gives an explicit natural bijection, we can use either definition for a greedoid. Most sources (such as Wikipedia) use an unordered version, but I find the ordered version to be much more intuitive for greedy algorithms.

        • »
          »
          »
          »
          »
          16 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Mind explaining the induction?

          • »
            »
            »
            »
            »
            »
            16 months ago, # ^ |
            Rev. 6   Vote: I like it +15 Vote: I do not like it

            Let's denote $$$g(f(L))$$$ as $$$L'$$$. In whatever follows, we'll implicitly use the fact that $$$L$$$ and $$$L'$$$ are simple languages.

            All characters of $$$L$$$ are present as singleton sets in $$$f(L)$$$ (and they are the only singletons), so all words of size $$$1$$$ in $$$L'$$$ are in $$$L$$$ too.

            It'll be more concise to use well-ordering instead of induction here to show that $$$L'$$$ is a subset of $$$L$$$ (same thing since they're equivalent). Consider a smallest word $$$w$$$ in $$$L'$$$ that is not in $$$L$$$ (if it exists). $$$w$$$ has size at least $$$2$$$. Since $$$L'$$$ is hereditary, $$$w[:-1]$$$ is in $$$L'$$$. But since $$$w$$$ is the smallest word in $$$L'$$$ that is not in $$$L$$$, $$$w[:-1]$$$ is in $$$L$$$ as well. Note that $$$f(L')$$$ is a subset of $$$f(L)$$$, so there is a word $$$w'$$$ in $$$L$$$ such that $$$f(w')$$$ = $$$f(w)$$$. Since $$$L$$$ is a greedoid, apply the exchange lemma on $$$w'$$$ and $$$w[:-1]$$$. This shows $$$w$$$ is in $$$L$$$, contradiction.

            So $$$L'$$$ is a subset of $$$L$$$, which means $$$L$$$ and $$$L'$$$ are identical, owing to the maximality of $$$L'$$$.