$\newcommand{\defeq}{\mathrel{\mathop:}=}$

2008/07/05

Interpreting a New Kind of Monotonicity

The following theorem is a slight generalisation from the original monotonicity and greedy theorem:

Thm. Let R : A ← A be a preorder and S : A ← FA
be monotonic on Rº in the sense that

S . FRº . Tº  ⊆  Rº . S

where T : FA ← FA satisfies

S . T  ⊆  S.

Then

min R . Λ⦇S⦈  ⊇  ⦇min R . ΛS . T⦈.

There is a way to interpret the new monotonicity condition:
  S . FRº . Tº   ⊆   Rº . S
y   b     a   a'   y    x   a'

Here we are comparing two partial solutions a and b, where b is worse than a. A complete solution y is generated from b. The monotonicity condition says that instead of choosing b as the input, we should take another partial solution a' which is transformed from a by T, since from a' one can generate another complete solution x which is better than y.

The interpretation is a bit strange, though. It seems that we are mixing two different levels of solutions. The premise compares a and b, but the conclusion is that a solution generated from b is worse than another solution generated from a', which is transformed from a.

      R
a ----- b
|       |
T |       |
↓       |
a'      | S
|       |
S |       |
↓       ↓
x ----- y
R

It seems to be more sensible if what the monotonicity says is like this:
      R
a ----- b
|       |
T |       | T
↓       ↓
a'      b'
|       |
S |       | S
↓       ↓
x ----- y
R

The partial greedy theorem is a special case of this theorem, where T is a coreflexive. When deriving the activity-selection problem, I do have to do some "coreflexive propagation" and fusion to make the monotonicity look like the second diagram. Maybe this peculiarity would be understood if we can solve some concrete problem by this theorem.

Another point to make: If T is entire, then the conditions of the theorem would imply the original monotonicity condition:

  S . FRº . Tº  ⊆  Rº . S
⇒  { composition is monotonic }
S . FRº . Tº . T  ⊆  Rº . S . T
⇒  { T entire }
S . FRº  ⊆  Rº . S . T
⇒  { S . T ⊆ S }
S . FRº  ⊆  Rº . S.

Then we can just apply the original greedy theorem and get rid of T. So this theorem is interesting only if T is not entire, which is just the case of partial greedy theorem.

And finally, we can also prove a similar variation of thinning theorem. This would potentially allow more problems to be solved by identifying this new kind of monotonicity.

--
More clarifications needed...

Labels: