a sequence that needs extending

[Dean Hickerson]

Rob Pratt wrote:

> At least for small n, the bound from solving the LP relaxation is n^2.

Too bad.

> Another empirical property gleaned from the optimal solutions I've seen is
> that cell (1,1) is colored 1 and cell (n,n) is colored n.  Can this
> property be shown to hold without loss of optimality?

Later:

> I meant cell (n,1) is colored 1 and cell (1,n) is colored n.

Actually, I prefer the original numbering, in which row numbers increase
from bottom to top.  (I usually start the numbering at 0, but I'll try
to remember to translate to 1 for this discussion.)

Anyway, yes.  If position (1,1) contains a symbol s>1, you can replace it
by the symbol 1 without affecting monotonicity:  Since you're decreasing
the minimal element in row 1, row 1 remains monotonic.  Similarly for
column 1.  And since the original row 1 and column 1 were monotonic, neither
contained symbol 1.  So the positive slope condition remains true.

Similarly (or by the 3-dimensional symmetry of the underlying geometric
problem), if either row 1 or column 1 contains symbol 1, you can delete it
there and insert it at (1,1).

Finally, if (1,1) is empty and neither row 1 nor column 1 contains symbol 1,
then you can add a 1 at (1,1).

Dean Hickerson
dean at math.ucdavis.edu


MIME-Version: 1.0