MQ- sorting measures serve other purposes, Adaptive Planar Graph Algorithms
Jérémy Barbay 15 Jun 201015/06/10 a las 17:07 hrs.2010-06-15 17:07:15
RMQ- sorting measures serve other purposes, Adaptive Planar Graph Algorithms, by Jeremy <2010-06-15 Tue 14:30-16:00>
***** RMQ
****** Johannes's results (and slides)
[[file:~/ ... ces/bibliography.org::* 28 Optimal Succinctness for Range Minnimum Queries Johannes Fisher]]
****** Adaptive intuition: discussion
file:~/ ... geMinimumQueries.org
1 General Runs
---------------
- detect them in linear time
- mark them using o(n) space
- apply usual structure to the heads of the runs
- when solving a query,
- ACCESS A for the first run intersected (hence this
example is a /systematic/ data structure)
- compute the min of the rest of the heads of the runs
intersected using the 2d min heap
- return the min of the two.
- given an array of r runs, this yields a /systematic/ data
structure of 2r+o(n) bits.
2 Strict Runs
--------------
- Same thing, but no need to access A, because all elements of a
strict runs are consecutive, hence the first element of the
interval of the query is the answer if and only if the head of
the strict run it belongs to is smaller than all other heads
contained in the query
- given an array of r strict runs, this yields a /non-systematic/
data structure of 2r+o(n) bits.
Those results are not enough
- we lose the separation of the index
- they are mere hacks: we should be able to do better!
****** Formalisation: better results
******* Jansson et al's scheme:
- To encode trees while supporting many operators (including those we need for RMQ)
- using nH(n_1,...,) bits where n_i = nb of nodes with $i$ children
******* Analysis of Jansson scheme encoding of 2d min heap tree in function of \rho
- \rho runs means \rho branches (and leaves) in the 2d min heap tree.
- [X] k strict runs
+ k branches starting at the root, which yields
- 1 root node of degree k
- k nodes of degree 0 and
- n-k-1 nodes of degree 1
- [X] k runs
+ k branches starting at arbitrary nodes, which yields
- at most k nodes of degree larger than one and smaller than k,
- exactly k nodes of degree 0 and
- at least n-2k nodes of degree 1
- Using Jansson et al [Ultra-succinct Representation of
Ordered Trees] one can represent the 2d-min-heap with less
than 2n bits when the distribution of the node's degree is
strongly skewed, which happens for instance in the 2d-min
heap of an array with \rho long runs (the tree will consist
only of \rho branches of nodes of degree 1, connected at
\rho nodes of degree 2).
******* Perspective?
- Formal computation
- Other measures? (REM)
- Finer Analysis, other data structure?
***** Planar Graphs
****** Planar Max Flow:
******* Definition
+ Given
- a /directed/ graph G=(V,E),
- a cost function c:E->R+,
- s,t \in V
+ Output a valid flow assignation to each edge, maximizing the
flow from s to t
******* Known Results
- The problem is O(n\lg n), no tight lower bound is known.
- There is a O(n) time algorithm to find the max flow when s and t
share a face [Hassin]
- The new analysis of the O(n\lg n) algorithm by E/B&K indicates
an adaptive component, dominated by the initialisation cost in
O(n\lg n).
****** Adaptive (s,t) MinCut
******* Definition of the Problem:
- Input
- G=(V,E) directed
- c:E->R+
- s,t\in V
- Output
- \pi\subset E s.t.
- \pi is a cut
- \pi minimize \pi(c)
******* Algorithm
1. In G^* find P=minpath(s^*,t^*)
- note *d* its lenght.
2. Replace each vertex v of P by v_L and v_R, disconnected,
such that
- edges of v on the left now connecto to v_L, and
- edges of v on the right no connect to v_R
3. Recursively, for point v of P in middle
- find minpath P_v between v_R and v_L, of value cP_v
- partition G into the higher part G_h and the lower part
G_l and recurse
4. Return the path of smallest cost cP_v
******* Result
- This algorithm was known [Hassin and Johnson 1985 for
undirected] to compute the (s,t)min cut in time O(n\lg n), and
to give the value of max flow.
- "new" analysis gives total time O(n+d+n\lg d)
- (mincut of the flow, which edges are saturated for max flow)
****** Self-Adjusting Top Trees: the shaddow of the beginning of an answer.
******* Definition
- Given a forest
- Choose an arbitrary root
- partition the forest into edge disjoint paths
- deduce (uniquely) from it a unique series of rakes and compress
- define (at most) lg n decomposition levels into *unit tree*
- Each unit tree is a spinal chord with unique trees on the
sides of each node, recursively encoded.
- Each unit tree is encoded by a balanced binary search tree
on the node of its spinal chord.
******* Results
- using splaying (cf Splay trees), unit-trees can be updated
dynamically in time O(\lg n) (amortized?)
- using an *expose* operator, one can add a constant value to
the (potential more than \lg n) edges of a path in time
O(\lg n) (amortized) -> useful for maxflow type problems.
******* Perspectives:
1. Self Adjusting Top Trees are *adaptive*: when path exposed
is very similar to the path previously exposed, there are
less changes in the structure: how to measure it?
2. In the maxflow problem, in worst case instances which seem
easy, the paths exposed are very similar... Can we have an
adaptive result here?
***** RMQ
****** Johannes's results (and slides)
[[file:~/ ... ces/bibliography.org::* 28 Optimal Succinctness for Range Minnimum Queries Johannes Fisher]]
****** Adaptive intuition: discussion
file:~/ ... geMinimumQueries.org
1 General Runs
---------------
- detect them in linear time
- mark them using o(n) space
- apply usual structure to the heads of the runs
- when solving a query,
- ACCESS A for the first run intersected (hence this
example is a /systematic/ data structure)
- compute the min of the rest of the heads of the runs
intersected using the 2d min heap
- return the min of the two.
- given an array of r runs, this yields a /systematic/ data
structure of 2r+o(n) bits.
2 Strict Runs
--------------
- Same thing, but no need to access A, because all elements of a
strict runs are consecutive, hence the first element of the
interval of the query is the answer if and only if the head of
the strict run it belongs to is smaller than all other heads
contained in the query
- given an array of r strict runs, this yields a /non-systematic/
data structure of 2r+o(n) bits.
Those results are not enough
- we lose the separation of the index
- they are mere hacks: we should be able to do better!
****** Formalisation: better results
******* Jansson et al's scheme:
- To encode trees while supporting many operators (including those we need for RMQ)
- using nH(n_1,...,) bits where n_i = nb of nodes with $i$ children
******* Analysis of Jansson scheme encoding of 2d min heap tree in function of \rho
- \rho runs means \rho branches (and leaves) in the 2d min heap tree.
- [X] k strict runs
+ k branches starting at the root, which yields
- 1 root node of degree k
- k nodes of degree 0 and
- n-k-1 nodes of degree 1
- [X] k runs
+ k branches starting at arbitrary nodes, which yields
- at most k nodes of degree larger than one and smaller than k,
- exactly k nodes of degree 0 and
- at least n-2k nodes of degree 1
- Using Jansson et al [Ultra-succinct Representation of
Ordered Trees] one can represent the 2d-min-heap with less
than 2n bits when the distribution of the node's degree is
strongly skewed, which happens for instance in the 2d-min
heap of an array with \rho long runs (the tree will consist
only of \rho branches of nodes of degree 1, connected at
\rho nodes of degree 2).
******* Perspective?
- Formal computation
- Other measures? (REM)
- Finer Analysis, other data structure?
***** Planar Graphs
****** Planar Max Flow:
******* Definition
+ Given
- a /directed/ graph G=(V,E),
- a cost function c:E->R+,
- s,t \in V
+ Output a valid flow assignation to each edge, maximizing the
flow from s to t
******* Known Results
- The problem is O(n\lg n), no tight lower bound is known.
- There is a O(n) time algorithm to find the max flow when s and t
share a face [Hassin]
- The new analysis of the O(n\lg n) algorithm by E/B&K indicates
an adaptive component, dominated by the initialisation cost in
O(n\lg n).
****** Adaptive (s,t) MinCut
******* Definition of the Problem:
- Input
- G=(V,E) directed
- c:E->R+
- s,t\in V
- Output
- \pi\subset E s.t.
- \pi is a cut
- \pi minimize \pi(c)
******* Algorithm
1. In G^* find P=minpath(s^*,t^*)
- note *d* its lenght.
2. Replace each vertex v of P by v_L and v_R, disconnected,
such that
- edges of v on the left now connecto to v_L, and
- edges of v on the right no connect to v_R
3. Recursively, for point v of P in middle
- find minpath P_v between v_R and v_L, of value cP_v
- partition G into the higher part G_h and the lower part
G_l and recurse
4. Return the path of smallest cost cP_v
******* Result
- This algorithm was known [Hassin and Johnson 1985 for
undirected] to compute the (s,t)min cut in time O(n\lg n), and
to give the value of max flow.
- "new" analysis gives total time O(n+d+n\lg d)
- (mincut of the flow, which edges are saturated for max flow)
****** Self-Adjusting Top Trees: the shaddow of the beginning of an answer.
******* Definition
- Given a forest
- Choose an arbitrary root
- partition the forest into edge disjoint paths
- deduce (uniquely) from it a unique series of rakes and compress
- define (at most) lg n decomposition levels into *unit tree*
- Each unit tree is a spinal chord with unique trees on the
sides of each node, recursively encoded.
- Each unit tree is encoded by a balanced binary search tree
on the node of its spinal chord.
******* Results
- using splaying (cf Splay trees), unit-trees can be updated
dynamically in time O(\lg n) (amortized?)
- using an *expose* operator, one can add a constant value to
the (potential more than \lg n) edges of a path in time
O(\lg n) (amortized) -> useful for maxflow type problems.
******* Perspectives:
1. Self Adjusting Top Trees are *adaptive*: when path exposed
is very similar to the path previously exposed, there are
less changes in the structure: how to measure it?
2. In the maxflow problem, in worst case instances which seem
easy, the paths exposed are very similar... Can we have an
adaptive result here?
| Última Modificación | 15 Jun 201015/06/10 a las 17:07 hrs.2010-06-15 17:07:15 |
|---|---|
| Vistas Únicas | 0 |
| Compartir |
