Adaptive to order and Structure: results and challenges
Jérémy Barbay 15 Jun 201015/06/10 a las 17:06 hrs.2010-06-15 17:06:15
Adaptive to order and Structure: results and challenges <2010-06-10 Thu 14:30-16:00>
1) Input order instance optimality, two problems
1. Improve the algorithm
- find unordered instance optimal algorithms which perform
better when the input is almost ordered (for various
measures).
- a trivial approach is to simulate two algorithms in
parallel, and stop as soon as one finishes => Dove tailing algorithm
- a more clever approach is to combine two algorithms in
one (e.g. \rho-adaptive with \sigma-adaptive)
2. Analyze the algorithm
- the algorithms seem only as good as the analysis:
- fixing only n does not permit to distinguish between
various algorithms.
- similarly, fixing only \sigma (or h) and \rho does not
permit to distinguish between the naive algorithm which
simulates in parallel two distinct algorithm and a more
clever one which combines them cleverly.
- there are (at least two solutions):
- define a better measure of difficulty
- define another "model" such as competive ratio between
algorithm, inspired by the work of Dorrigiv and
Lopez-Ortiz on online algorithms.
2) Improving the algorithm in function of \rho and \sigma
1. Sorting
- Roughly outlined already by Munro and Spira: even if they
did not consider adaptive algorithms, they considered the
(adaptive) complexity of insertion sort and merge sort in
function of \sigma, and it is easy to show that the
adaptive versions of insertion sort and merge sort are at
once adaptive to \rho and \sigma.
2. Planar Convex Hull
- The equivalent of Run can be defined in several ways. I
define it in non-convex paths.
- From there, using linear merging, we have a similar
algorithm to adaptive merge sort.
- making it adaptive to h (i.e. \sigma) is only a matter of
interleaving one of Chan's gift-wrapping's step between
two merge steps.
3. 3d Convex Hull
- The equivalent of Run might be defined in several ways. I
define it in function of Jack Snoeyink linear encoding of
triangulations (which encodes a 3d convex hull).
- From there, using linear merging from Kirpatrick, we have
a similar algorithm to adaptive merge sort.
- Similarly to 2d, interleaving steps yields an algorithm
adaptive to both \sigma and \rho (and more, to the
distribution of the sizes of the runs, or of the
distribution of the scopes of the points in the
certificate)
3) Improving the analysis (more vague)
1. Certificates.
- each correct algorithm must be able to print some
"certificate" that its answer is correct. Let's consider
this as the real output of the algorithm.
- MAYBE one can show that the \rho adaptive and \sigma
adaptive use a different "grammar" each, and use this to
define the "shortest certificate" using the union of the
two grammars.
- Then one would have a new measure of difficulty for the problem.
- But one would have to justify why not consider another
grammar/vocabulary, in particular corresponding to other
orders (Subsequences arbitrary SUS or SMS, subsequences
regular)
2. Codificacion
- Each algorithm defines an encoding of the certificate, and
in essence of the instance.
- An algorithm which use special order will have to encode
it, which is not taken into account in the current models,
but would be taken into account in a model counting the
space of the algorithm along the space of the certificate
of its execution.
3. Competitive/Collaborative Ratio
- Can we show a bound on the ratio between
- the complexity of the naive "Dove tailing"?
- the space taken by the algorithm+certificate?
4) Open Problems
- Algorithms adaptive to both order (other than Runs) and instance optimal
- A general *Synergy* technique to mix any adaptive algorithms,
finer than the *Dove Tailing* technique.
- An analysis for this.
1) Input order instance optimality, two problems
1. Improve the algorithm
- find unordered instance optimal algorithms which perform
better when the input is almost ordered (for various
measures).
- a trivial approach is to simulate two algorithms in
parallel, and stop as soon as one finishes => Dove tailing algorithm
- a more clever approach is to combine two algorithms in
one (e.g. \rho-adaptive with \sigma-adaptive)
2. Analyze the algorithm
- the algorithms seem only as good as the analysis:
- fixing only n does not permit to distinguish between
various algorithms.
- similarly, fixing only \sigma (or h) and \rho does not
permit to distinguish between the naive algorithm which
simulates in parallel two distinct algorithm and a more
clever one which combines them cleverly.
- there are (at least two solutions):
- define a better measure of difficulty
- define another "model" such as competive ratio between
algorithm, inspired by the work of Dorrigiv and
Lopez-Ortiz on online algorithms.
2) Improving the algorithm in function of \rho and \sigma
1. Sorting
- Roughly outlined already by Munro and Spira: even if they
did not consider adaptive algorithms, they considered the
(adaptive) complexity of insertion sort and merge sort in
function of \sigma, and it is easy to show that the
adaptive versions of insertion sort and merge sort are at
once adaptive to \rho and \sigma.
2. Planar Convex Hull
- The equivalent of Run can be defined in several ways. I
define it in non-convex paths.
- From there, using linear merging, we have a similar
algorithm to adaptive merge sort.
- making it adaptive to h (i.e. \sigma) is only a matter of
interleaving one of Chan's gift-wrapping's step between
two merge steps.
3. 3d Convex Hull
- The equivalent of Run might be defined in several ways. I
define it in function of Jack Snoeyink linear encoding of
triangulations (which encodes a 3d convex hull).
- From there, using linear merging from Kirpatrick, we have
a similar algorithm to adaptive merge sort.
- Similarly to 2d, interleaving steps yields an algorithm
adaptive to both \sigma and \rho (and more, to the
distribution of the sizes of the runs, or of the
distribution of the scopes of the points in the
certificate)
3) Improving the analysis (more vague)
1. Certificates.
- each correct algorithm must be able to print some
"certificate" that its answer is correct. Let's consider
this as the real output of the algorithm.
- MAYBE one can show that the \rho adaptive and \sigma
adaptive use a different "grammar" each, and use this to
define the "shortest certificate" using the union of the
two grammars.
- Then one would have a new measure of difficulty for the problem.
- But one would have to justify why not consider another
grammar/vocabulary, in particular corresponding to other
orders (Subsequences arbitrary SUS or SMS, subsequences
regular)
2. Codificacion
- Each algorithm defines an encoding of the certificate, and
in essence of the instance.
- An algorithm which use special order will have to encode
it, which is not taken into account in the current models,
but would be taken into account in a model counting the
space of the algorithm along the space of the certificate
of its execution.
3. Competitive/Collaborative Ratio
- Can we show a bound on the ratio between
- the complexity of the naive "Dove tailing"?
- the space taken by the algorithm+certificate?
4) Open Problems
- Algorithms adaptive to both order (other than Runs) and instance optimal
- A general *Synergy* technique to mix any adaptive algorithms,
finer than the *Dove Tailing* technique.
- An analysis for this.
| Última Modificación | 15 Jun 201015/06/10 a las 17:06 hrs.2010-06-15 17:06:15 |
|---|---|
| Vistas Únicas | 0 |
| Compartir |
