text:
\section{Introduction}
In computer science, a hash table~\cite{bookC:09} is a data structure that maps items (keys) to locations (values) using a hash function. More precisely, given a universe $U$ of items and a hash table $H$ of size $n \in \mathbb{N}$, a hash function
$h : U \rightarrow \{1,2,\ldots, n\}$ maps the items from $U$ to the $n$ positions on the table. Ideally, the hash function should assign to each possible item to a unique location, but this objective is rarely achievable in practice. Two or more items could be mapped to the same location resulting in a collision. In this work we deal with a collision resolution technique known as \emph{cuckoo hashing}.  Cuckoo hashing was first proposed by Pagh and Rodler in \cite{inp:pr01}. We are interested in a generalization of the original idea (see~\cite{inc:fpss03}) where we are given a table with $n$ locations, and we assume each location can hold a single item. Each item chooses randomly $k\ge 3$ locations (using $k$ random hash functions) and has to be placed in one of them.  Formally speaking we are given $k\ge3$ hash functions $h_1, . . . , h_k$
that each maps an element $x \in U$ to a position in the table $H$.
Moreover we assume that $h_1, . . . , h_k$ are truly independent and random hash functions. We refer the reader to ~\cite{ms:08,d:09}  (and references therein) for justification of this idealized assumption.
 Other variations of cuckoo hashing are considered in for example \cite{inp:ans:09,art:kmw09}.

Cuckoo hashing resembles multiple choice allocations schemes in the sense that it allows more than one choice for a single item. In addition it supports dynamically changing the location of an item among its possible locations during insertion. The insertion procedure in cuckoo hashing goes as follows. Assume that $p$ items have been inserted, each of them having made their $k$ random choices on the hash table, and we are about to insert the $p+1$st item. This item selects its $k$ random locations from the hash table and is assigned to one of them. But this location might already be occupied by a previously inserted item. In that case, the previous item is evicted or ``kicked out'' and is assigned to one of the other $k-1$ selected locations. In turn, this position might be occupied by another item, which is kicked out and goes to one of the remaining $k-1$ chosen locations. This process may be repeated indefinitely or until a free loction is found.

We model cuckoo hashing by a directed graph $G=(V,E)$  such that the set of vertices $V=\{v_1,v_2,\ldots,v_n\}$ corresponds to locations on the hash table. We say a vertex is \emph{occupied} if there is an item assigned to the corresponding location, otherwise it is \emph{free}. Let $\mathcal{I}$ be the set of $m$ items. We represent each item $x\in\mathcal{I} $ as a tuple of its $k$ chosen vertices (locations), for example, $x=(v_{x_1},v_{x_2},\ldots , v_{x_k})$.
A directed edge $e=(v_i,v_j) \in E$ if and only if there exists an item $y\in \mathcal{I} $ so that the following two conditions hold, (i) $v_i,v_j \in y$, and (ii) $v_i$ is occupied by $y$. Note that a vertex with outdegree $0$ is a free vertex. We denote the set of free vertices by $F$ and the distance of any vertex $v$ from some vertex in $F$ by $d(v,F)$. Since $G$ represents an allocation we call $G$ an \emph{allocation graph}.

Now assume that in the cuckoo insertion procedure, at some instance an item $z$ arrives such that all its $k$ choices are occupied. Let $v_j\in z$ be the vertex chosen to place item $z$. The following are the main observations.

 \begin{enumerate}
\item The necessary condition for item $z$ to be successfully inserted at $v_{z_j}$ is the existence of a path from $v_{z_j}$ to $F$. This condition remains satisfied as long as some allocation is possible.
\item The procedure will stop in the minimum number of steps if for all $v_{z_i}\in z$  the distance $d(v_{z_j},F)\le d(v_{z_i},F)$. \end{enumerate}

With respect to our first observation, a natural question to ponder would be the following. We are given a set of $m$ items and $n$ locations such that each item picks $k\ge 3$ locations at random. Is it possible to place each of the items into one of their chosen locations such that each location holds at most one item? From~ \cite{inp:l12,fp12,fm12} we know that there exists a critical size $c_k^* n$ such that if $m<c_k^* n$ then such an allocation is possible with high probability, otherwise this is not the case.

\begin{theorem}
\label{thm:mainO}
For integers~$k\geq 3$ let~$\xi^\ast$ be the unique solution of the equation
\begin{equation}\label{eq:kxi}
 k = {\xi(1-e^{-\xi})\over 1-e^{-\xi} -\xi e^{-\xi} }.
\end{equation}
Let~$c_{k}^\ast= \frac{\xi^\ast}{k(1-e^{-\xi^{*}})^{k-1}}$. Then
\begin{equation}
\label{eq:phnmkl}
	\Pr{\text{allocation of $m=\lfloor cn\rfloor$ items to $n$ locations is possible}}
	\stackrel{(n \to \infty)}{=}
	\begin{cases}
		0, & \text{ if } c > c_{k}^\ast \\
		1, & \text{ if } c < c_{k}^\ast
	\end{cases}.
\end{equation}
\end{theorem}

The proof of the above theorem is non-constructive, i.e., it does not give us an algorithm to find such an allocation. In this work we deal with the algorithmic issues and propose an algorithm which takes linear time with high probability and in expectation to find the optimal allocation.

Our second observation suggests that the insertion time in the cuckoo hashing depends on the selection of the location, which we make for each assignment, from among the $k$ possible locations. One can in principle use breadth first search to  always make assignments over the shortest path (in the allocation graph). But this method is inefficient and expensive to perform for each item. One can also select uniformly at random a location from the available locations. This resembles a random walk on the locations of the table and is called the \emph{random walk insertion}. In~\cite{art:fps10,art:fmm11} the authors analyzed the random walk insertion method and gave a polylogarithmic bound (with high probability) on the maximum insertion time, i.e., the maximum time it can take to insert a single item.

\subsection{More on Related Work}
The allocation problem in cuckoo hashing can also be phrased in terms of \emph{orientation of graphs} or more generally \emph{orientations of $k$-uniform hypergraphs}. The $n$ locations are represented as vertices and each of the $m$ items form an edge with its $k$-vertices representing the $k$ random choices of the item.
In fact, this is a random (multi)hypergraph $H^*_{n,m,k}$ (or random (multi)graph $G^*_{n,m}$ for $k=2$) with $n$ vertices and $m$ edges where each edge is drawn uniformly at random ( with replacement) from the set of all $k$-multisubsets of the vertex set. An $\ell$-orientation of a graph then amounts to a mapping of each edge to one of its vertices such that no vertex receives more than $\ell$ edges. $\ell$ is also called the maximum load capacity. In our algorithm, we focus on $\ell=1$. Here, we give an overview of existing work for general $\ell$ for completeness.

For the case $k = 2$, several allocation algorithms and their analysis are closely connected to the cores of the associated
graph. The $\ell$ core of a graph is the maximum vertex induced subgraph with minimum degree at least $\ell$. As another application, the above described problem can also be seen as a load balancing problem with locations representing the \emph{machines} and the items representing the \emph{jobs}. To this extent Czumaj and Stemann~\cite{ina:cs01} gave a linear time algorithm achieving maximum load $O(m/n)$ based on computation of all cores. The main idea was to repeatedly choose a
vertex $v$ with minimum degree and remove it from the graph, and assigning all its incident edges (items) to vertex (location) $v$. Cain, Sanders, and Wormald~\cite{1283433}  used a variation of the above approach and gave a linear time algorithm for computing an optimal allocation (asymptotically almost surely). Their algorithm first guesses the optimal load among the two likely values values ($\lceil m/n\rceil $ or $\lceil m/n\rceil +1$). The procedure starts with a load value say $\ell=\lceil m/n\rceil $. Each time a vertex with degree at most $\ell$ and its incident edges are assigned to $v$. The above rule, also called the \emph{mindegree rule}, first reduces the graph to its $\ell+1$ core. Next, some edge $(u,v)$ is picked according to some priority rule and assigned to one of its vertices. Again the mindegree rule is applied with respect to some conditions. In case the algorithm fails it is repeated after incrementing the load value.

Fernholz and Ramachandran~\cite{1283432} used a different approach in dealing with the vertices with degree greater than the maximum load.  Their algorithm, called the \emph{excess degree reduction} (EDR) approach, always chooses a vertex with minimum degree, $d$. If $d<\ell$ then this vertex is assigned all its incident edges and is removed from the graph. In case $d>2\ell$ the algorithm fails. Otherwise, EDR replaces $d-\ell$ paths of the form
$(u, v, w)$ by bypass edges $(u, w)$ and then orients all remaining edges ($\le \ell$ ) incident to $v$
towards $v$.

\noindent Optimal allocations can also
be computed in polynomial time using maximum
flow computations and with high probability achieve a maximum load of
$\lceil m/n\rceil$ or $\lceil m/n\rceil +1$~\cite{sek99}.

Very recently Aum{\"u}ller, Dietzfelbinger and Woelfel~\cite{art:aumuller16} analyzed our algorithm in their special framework of an easily computable hash class.

\paragraph{Notations.} Throughout the paper we use the following notations. We denote the set of integers $\{1,2,\ldots, n\}$ by $[n]$. Let $V=\{v_1,v_2,\ldots, v_n\}$ be the set of $n$ vertices representing the locations of the hash table. For an allocation graph $G=(V,E)$ and any two vertices $v_i,v_j\in V$, the shortest distance between $v_i$ and $v_j$ is denoted by $d(v_i,v_j).$  We denote the set of free vertices by $F$. We denote the shortest distance of a vertex $v_i\in V$ to any set of vertices say $S$ by $d(v_i,S)$ which is defined as \[d(v_i,S): = \min_{v_j\in S} d(v_i,v_j).\] We use $R$ to denote the set of vertices furthest from $F$, i.e.,
\[   R:= \{ v_i\in V |d(v_i, F ) \ge \max_{ v_j \in V} d(v_j,F)\}.
\]

For some integer $t\in[n]$ and the subset of vertex set $V' \subset V$ let ~$N_{t}(v_i)$ and $N_{t}(V')$ denote the set of vertices at distance at most $t$ from the vertex $v_i \in V$ and the set $V'$. Mathematically,
\[ N_{t}(v_i) := \{ v_j \in V~| ~d(v_i,v_j) \le t  \} \]
and
\[ N_{t}(V') := \{ v_j \in V~| ~d(v_i,V') \le t  \} .\]
\subsection{Our Contribution}
Our aim here is to minimize the total insertion time in cuckoo hashing, thereby minimizing the total time required to construct the hash table. We propose a deterministic strategy of how to select a vertex for placing an item when all its choices are occupied.
We assign to each vertex $v_i\in V$ an integer label, $L(v_i)$. Initially all vertices have $0$ as their labels. Note that at this stage, for all  $j\in [n]$, $L(v_j) =d(v_j,F)$, i.e., the labels of all vertices represent their shortest distances from $F$. When an item $x$ appears, it chooses the vertex with the least label from among its $k$ choices. If the vertex is free, the item is placed on it. Otherwise, the previous item is kicked out. The label of the location is then updated and set to one more than the minimum label of the remaining $k-1$ choices of the item $x$. The kicked out item chooses the location with minimum label from its $k$ choices and the above procedure is repeated till an empty location is found.
Note that to maintain the labels of the vertices as their shortest distances from $F$ we would require to update labels of the neighbors of the affected vertex and the labels of their neighbors and so on. This corresponds to performing a breadth first search (bfs) starting from the affected vertex. We avoid the bfs and perform only local updations. Therefore, we also call our method as \emph{local search allocation}.

Previous work~\cite{inc:fpss03} on total allocation time has analysed breadth first search, and it was shown  to be linear only in \emph{expectation}.  The local search allocation method requires linear time with probability $1-o(1)$  and in expectation to find an allocation. We now state our main result.

\begin{theorem}\label{thm:main}
Let $k\ge 3$. For any fixed $\varepsilon >0$, set $m=(1-\varepsilon) c_k^* n$.  Assume that each of the $m$ items chooses $k$ random locations (using $k$ random hash functions) from a table with $n$ locations. Then for some $\zeta>0$with probability $1-n^{-\zeta}$, LSA finds an allocation of these items (such that no location holds more than one item) in time O(n). Moreover the expected running time of LSA is also O(n).
\end{theorem}
We prove the above theorem in two steps. First we show that the algorithm is correct and finds an allocation in polynomial time. To this end we prove that, at any instance, label of a vertex is at most its distance from the set of free vertices. Therefore, no vertex can have a label greater than $n$. This would imply that the algorithm could not run indefinitely and would stop after making at most $n$ changes at each location.
We then show that the local search insertion method will find an allocation in a time proportional to the sum of distances of the $n$ vertices from $F$ (in the resulting allocation graph).
We then complete the proof by showing that  $(i)$ if for some $\varepsilon >0$, $m=(1-\varepsilon)c^*_k$ items are placed in $n$ locations using $k$ random hash functions for each item then the corresponding allocation graph has two special structural properties with probability $1-o(1)$, and $(ii)$ if  the allocation graph has these two properties, then the sum of distances of its vertices from $F$ is linear in $n$. In the next section we give a formal description of our algorithm and its analysis.
\subsection*{Cuckoo Hashing and Random Hypergraphs}
As already mentioned we can model the allocation problem in cuckoo hashing as a hypergraph. Each location can be viewed as a vertex and each item as an edge. The $k$ vertices of each edge represent its $k$-random choices. In fact, this is a random hypergraph  with $n$ vertices and $m$ edges where each edge is drawn uniformly at random (with replacement) from the set of all $k$-multisubsets of the vertex set.
Therefore, a proper allocation of items is possible if and only if~the corresponding hypergraph is~\emph{$1$-orientable}, i.e., if there is an assignment of each edge $e\in E$ to one of its vertices $v\in e$ such that each vertex is assigned at most one edge. We denote a random (multi)hypergraph with $n$ vertices and $m$ edges by $H_{n,m,k}$.
We define the \emph{density} of a hypergraph as the ratio of the number of edges to the number to its vertices.

We will need the following results from \cite{art:fps10} about the expansion properties of a random hypergraph. In the analysis of LSA we would see that these properties help us to infer that the allocation graph expands considerably and the maximum label of any vertex there is $O(\log n)$.
\begin{theorem}\label{thm:density}
Let for any fixed $\varepsilon>0$, $m=(1-\varepsilon)c^*_k n$. Then there exists a $\delta =\delta(\varepsilon,k)$ such that any subhypergraph of $H_{n,m,k}$ has density at most $(1-\delta)$ with probability $1-O(1/n)$.
\end{theorem}
The proof of the following lemma is similar to that in \cite{art:fps10}. The parameters here are adjusted to our requirements; so we present the proof for completeness.

\begin{lemma}\label{lem:expanhyper}
Let $m<c_k^*n$ and $\alpha < {1/(k-1)}$. Then for every integer $s$ such that $1\le s \le\alpha n$,  there exists a constant $\zeta>0$ such that the following holds with probability $1-n^{-\zeta}$.  The number of vertices spanned by any set of edges of size $s$ in $H_{n,m,k}$ is greater than $ \left( k-1- {\log(k-1)e^{k} \over \log{1\over \alpha(k-1)}}\right)s$.
\end{lemma}
\begin{proof}
Recall that each edge in $H_{n,m,k}$ is a multiset of size $k$. Therefore, the probability that an edge of  $H_{n,m,k}$ is contained completely in a subset of size $t$ of the vertex set  is given by ${t^k\over n^k}$.
Thus the expected number of sets of edges of size $s$ that span at most $t$ vertices is at most
${m\choose s}{n\choose t} \left({t^k\over n^k}\right)^{s}.$
Note that  by the following approximation for factorials for positive integer $a$
\[\left({a\over e}\right)^a  \sqrt{2\pi a}\le a! \le \left({a\over e}\right)^a e \sqrt{a} ,
\]
we obtain for $0<b<a$
\begin{align*}
{a\choose b} = {a! \over b! (a-b)! }\le &{ \left({a\over e}\right)^a e \sqrt{a}\over \left({b\over e}\right)^b \left({a-b\over e}\right)^{a-b}\sqrt{2\pi b}\sqrt{2\pi (a-b)}} = {e\over 2\pi}\cdot \left( 1-{b\over a}\right)^{-(a-b+1/2)}\left({a\over b}\right)^b \\
<&{\exp\left(1+b+ {b\over 2a} + {b^2\over 2a^2}-{b^3\over a^2} \right) \over 2\pi}\left({a\over b}\right)^b < {\exp\left( 1+{b\over 2a} -{b^3\over 2a^2}\right) \over 2\pi}\left({ae\over b}\right)^b\\
&<{ \exp(1.5) \over 2\pi}\left({ae\over b}\right)^b < \left({ae\over b}\right)^b.
\end{align*}
Using the above bounds for $m<c^*_k n$  and setting $t= (k-1-\delta_s)s$ we obtain
\begin{align*}\label{eq:expan}
{m\choose s}{n\choose t} \left({t\over n}\right)^{ks} < & \left({nc^*_ke\over s}\right)^s  \left({ne\over t}\right)^t \cdot \left({t\over n}\right)^{ks}<  \left({nc^*_ke\over s}\right)^s  \left({ne\over t}\right)^t \cdot \left({t\over n}\right)^{ks} \\
= &\left({nc^*_k\over s}\right)^s  \left({n\over t}\right)^{t-ks} e^{t+s}
= \left({nc^*_ke^{k-\delta_s}\over s}\right)^s \left({n\over (k-1-\delta_s)s}\right)^{-(1+\delta_s)s}\\
<&  \left({nc^*_k\over s}\right)^s \left({n\over (k-1)s}\right)^{-(1+\delta_s)s} e^{ks} \\
= & \left(\left({n\over (k-1)s}\right)^{-\delta_s} \cdot (k-1){e^{k} c^*_k}\right)^s .
\end{align*}
Moreover from~\cite{fp12} we know that $c^*_k <1.$ Let $\beta$ be such that $(1+\beta)c^*_k =1$.
Setting  $\delta_s = {\log (k-1)e^{k} / \log {n\over s(k-1)}}$ we obtain
\[ \left(\left({n\over (k-1)s}\right)^{-\delta_s} \cdot (k-1){e^{k} c^*_k}\right)^s = (1+\beta)^{-s}.\]
Therefore, for $\delta_s = {1+\ln_{k-1}e^{k} / \ln_{k-1}{n\over s}-1}$ and $\alpha< {1/( k-1)}$, the probability that there exists a set  of edges of size $s$, where $n^{1/2}\le s\le \alpha n$, spanning at most $(k-1-\delta_s) s$ vertices is $O((1+\beta)^{-n^{1/2}}) =e^{-O(n^{1/2})}$

Note that for $n^{1/2}\le s\le \alpha n$, $\delta_s < {1+\log_{k-1}e^{k}/(\log_{k-1}{1\over \alpha}-1)}$.
For the case $1\le s<n^{1/2}$, we substitute $\delta_s= {\log (k-1)e^{k}/(\log {1\over \alpha(k-1)}-1})$.
Then the expected number of sets of edges of size $s$  spanning at most $(k-1- \delta_s)s $ vertices is at most
\begin{equation*}
\begin{split}
  \left(\left({ (k-1)n^{1/2} \over n}\right)^{\log (k-1)e^{k} \over \log {1\over \alpha(k-1)}-1} \cdot ((k-1)e^{k}) \right)^s.    \end{split}
\end{equation*}
Therefore for large $n$ the probability that there exists a set  of edges of size $1\le s< n^{1/2}$ spanning at most $\left(k-1-{\log (k-1)e^{k} \over \log {1\over \alpha(k-1)}}\right) s$ vertices is at most $o(n^{-1/2})$, which completes the proof .
\end{proof}

\section{Local Search Insertion and its Analysis}
Assume that we are given items in an online fashion, i.e., each item chooses its $k$ random locations whenever it appears. Moreover, items appear in an arbitrary order.  The insertion using local search method goes as follows. For each vertex $v\in V$ we maintain a label. Initially each vertex is assigned a label $0$. To assign an item $x$ at time $t$ we select one of its chosen vertices $v$ such that its label is minimum and assign $x$ to $v$. We assign a new label to $v$ which is one more than the minimum label of the remaining $k-1$ choices of $x$. However,  $v$ might have already been occupied by a previously assigned item $i'$. In that case we kick out $y$ and repeat the above procedure. Let $\mathbf{L}= \{ L(v_1), \ldots, L(v_n)\}$  and $\mathbf{T}= \{ T(v_1), \ldots, T(v_n)\}$ where $L(v_i)$ denotes the label of vertex $v_i$ and $T(v_i)$ denotes the item assigned to vertex $v_i$.  We initialize $\mathbf{L}$ with all $0$s , i.e., all vertices are free. We then use Algorithm~\ref{algo:orientEdge} to assign an arbitrary item when it appears.
\begin{algorithm}[h!]
\caption{AssignItem ($x, \mathbf{L},\mathbf{T}$)}
\label{algo:orientEdge}
\begin{algorithmic}[1]
\STATE Choose a vertex $v$ among the $k$ choices of $x$ with minimum label $L(v)$.
\keyword{if}{$(L(v)>=n-1)$ }
\STATE $\mathbf{EXIT}$  ~~~~~~~~~~~~~~~~~~~~~~~ $\rhd${\textbf{Allocation does not exist}}
\keyword{else}
\STATE $L(v) \leftarrow 1+ \min{(L(u)| u \neq v \text{~and $u \in x$})}$
\keyword{if}{$(T(v)\neq \emptyset )$}
\STATE $y\leftarrow T(v)$~~~~~~~~~~~~~~~~~~ $\rhd${\textbf{Move that replaces an item}}
\STATE $T(v) \leftarrow x$
\STATE $\mathbf{CALL}$ {AssignItem($y, \mathbf{L},\mathbf{T}$)}
\keyword{else}
\STATE $T(v) \leftarrow x$ ~~~~~~~~~~~~~~~~~~ $\rhd${\textbf{Move that places an item}}
\ENDIF
\ENDIF
\end{algorithmic}
\end{algorithm}
In the next subsection we first prove the correctness of the algorithm, i.e, it finds an allocation in a finite number of steps whenever an allocation exists. We show that the algorithm takes a maximum of $O(n^2)$ time before it obtains a mapping for each item. We then proceed to give a stronger bound on the running time.

\subsection{Labels and the Shortest Distances } \label{sec:proof}
We need some additional notation. In what follows  a \emph{move} denotes either placing an item in a free vertex or replacing a previously allocated item.
Let $M$ be the total number of moves performed by the algorithm. For $p\in [M]$ we use $L_p(v)$ to denote the label of vertex $v$ at the end of the $p$th move. Similarly we use $F_p$ to denote the set of free vertices at the end of $p$th move. The corresponding allocation graph is denoted as $G_p=(V,E_p)$.
We need the following proposition.
\begin{proposition}\label{prop:lev}
For all $p\in[M]$ and all $v\in V$, the shortest distance of $v$ to $F_p$ is at least the label of $v$, i.e., $d(v,F_p)\ge L_p(v)$.
\end{proposition}
\begin{proof}
We first note that the label of a free vertex always remain $0$, i.e.,
\begin{align}\label{obs1} \forall p\in [M], \forall w\in F_p, ~~~~~L_p(w)=0. \end{align}
We will now show that throughout the algorithm the label of a vertex is at most one more than the label of any of its immediate neighbors (neighbors at distance $1$). More precisely,
\begin{align}\label{obs2}
\forall p\in [M], \forall (u,v)\in E_p, ~~~~~ L_p(u)\le L_p(v)+1. \end{align}
We prove \eqref{obs2} by induction on the number of moves performed by the algorithm. Initially when no item has appeared all vertices have $0$ as their labels. When the first item is assigned, i.e., there is a single vertex say $u$ such that $L_1(u)=1$. Clearly, \eqref{obs2} holds after the first move. Assume that \eqref{obs2} holds after $p$ moves.

For the ($p+1$)th move let $w\in V$ be some vertex which is assigned an item $x$. Consider an edge $(u,v)\in E_p$ such that $u\neq w$ and $v\neq w$. Note that the labels of all vertices $v \in V\setminus w$ remain unchanged in the ($p+1$)th move. Therefore by induction hypothesis, \eqref{obs2} is true for all edges which does not contain $w$. By Step $2$ of Algorithm~\ref{algo:orientEdge} the new label of $w$ is one more than the minimum of the labels of its $k-1$ neighbors, i.e, \[L_{p+1}(w) =  \min_{w'\in x\setminus w} L_{p+1}(w') +1.\] Therefore \eqref{obs2} holds for all edges originating from $w$. Now consider a vertex $u\in V$ such that $(u,w)\in E_p$. Now by induction hypothesis we have $L_{p+1}(u)=L_p(u)\le L_p(w) +1.$ Note that the vertex $w$ was chosen because it had the minimum label among the $k$ possible choices for the item $x$, i.e.,
\[ L_p(w) \le \min_{w'\in x} L_{p} (w') = \min_{w'\in x\setminus w} L_{p+1} (w') < L_{p+1}(w).\] We therefore obtain
$ L_{p+1}(u)\le L_p(w) +1 < L_{p+1}(w) +1,$
thereby completing the induction step.
We can now combine \eqref{obs1} and \eqref{obs2} to obtain the desired result. To see this, consider a vertex $v$ at distance $s< n$ to a free vertex $f\in F_p$ such that $s$ is also the shortest distance from $v$ to $F_p$.  By iteratively applying \eqref{obs2} we obtain $L_p(v) \le s+ L_p(f) =d(v,F_p)$, which completes the proof.
\end{proof}
We know that whenever the algorithm visits a vertex, it increases its label by at least 1. Trivially the maximum distance of a vertex from a free vertex is $n-1$ (if an allocation exists), and so is the maximum label. Therefore the algorithm will stop in at most $n(n-1)$ steps, i.e., after visiting each vertex at most $n-1$ times, which implies that the algorithm is correct and finds an allocation in $O(n^2)$ time. In the following we show that the total running time is proportional to the sum of labels of the $n$ vertices.
\begin{lemma}\label{lem:graph}
Let $\mathbf{L^*}$ be the array of labels of the vertices after all items have been allocated using Algorithm~\ref{algo:orientEdge}. Then the total time required to find an allocation is $O(\sum_{v\in V} L^*(v))$.
\end{lemma}
\begin{proof}
Now each invocation of Algorithm \ref{algo:orientEdge} increases the label of the chosen vertex by at least 1. Therefore, if a vertex has a label $\ell$ at the end of the algorithm then it has been selected (for any move during the allocation process) at most $\ell$ times. Now the given number of items can be allocated in a time proportional to the number of steps required to obtain the array $\mathbf{L}^*$ (when the initial set consisted of all zeros)  and hence is $O(\sum_{v\in V} L^*(v))$.
\end{proof}
For notational convenience let $F:= F_M$ and $G:= G_M$ denote the set of free vertices and the allocation graph (respectively) at the end of the algorithm.
By Proposition~\ref{prop:lev}  we know that for each $v\in V$, $L^*(v) \le d(v,F)$. Moreover, by Step $2$ of Algorithm~\ref{algo:orientEdge} the maximum value of a label is $n$.
Thus the total sum of labels of all vertices is bounded as follows.\[\sum_{v_i\in V} L^*(v_i)) \le \min\left(\sum_{v_i\in V}d(v,F), n^2\right).\]
So our aim now is to bound the shortest distances such that the sum of these is linear in the size of $G$. We accomplish this in the following section.
 %
\subsection{Bounding the Distances }
To compute the desired sum, i.e., $\sum_{v_i\in V}d(v,F)$, we study the structure of the allocation graph. The following lemma states that, with probability $1-o(1)$, a fraction of the vertices in the allocation graph are at a constant distance to the set of free vertices, $F$. This would imply that the contribution for the above sum made by these vertices is $O(n)$.

\begin{lemma}\label{lem:dist}
For any fixed $\varepsilon>0$, let $m=(1-\varepsilon) c_k^* n$ items are assigned to $n$ locations using $k$ random choices for each locations. Then the corresponding allocation graph $G=(V,E)$ satisfies the following with probability $1-O(1/n)$: for every $\alpha >0$ there exist $C=C(\alpha, \varepsilon) >0$ and a set $S \subseteq V$ of size at least $(1-\alpha)n$ such that every vertex $v\in S$ satisfies $d(v,F)\le C$. \end{lemma}

\begin{proof}
We perform the following stripping process on $G$.
We start with $G$ and in each step remove all its free vertices and the edges they are contained in. Note that by removing the edges, we have removed the items placed on the corresponding vertices, thereby creating a new set of free vertices. For step $i$ of the stripping process, we denote the set of vertices by $V_i$ and the set of free vertices by $F_i$ and let $G_i$ be the corresponding allocation graph. The number of occupied vertices in $G_i$ is then equal to $|V_i|-|F_i|$. As each vertex holds at most one item, the number of remaining balls is $|V_i|-|F_i|$.

Let $H=(V,E')$ be a $k$-uniform hypergraph with $n$ vertices representing the locations and $m$ edges representing the items. Each edge consists of $k$ vertices or $k$ choices of the item.
Note that the number of occupied vertices in $G$ is equal to the number of edges in $H$. Similarly $G_i$ corresponds to a subgraph in $H$ induced on the vertex set $V_i$. Let us denote it by $H[V_i]$.
The number of occupied vertices in $G_i$, i.e. $|V_{i}|-|F_{i}|$, then is the number of edges in $H[V_i]$. By Theorem~\ref{thm:density}, with probability $1-o(1)$ we have $|F_{i}|\ge \delta |V_{i}|$.  Also by the stripping process we obtain $|V_{i+1}| = |V_{i}|- |F_{i}| $. We can therefore conclude that, with probability $1-o(1)$,  $|V_{i+1}| \le (1-\delta) |V_{i}|$.
Therefore, after $t\ge 1$ iterations of removing free vertices we obtain  $|V_{t}|\le (1-\delta )^{t}|V|$. We can now choose $t=\lceil{\ln_{(1-\delta)}\alpha}\rceil$ to deduce that $ |V_{t}| <\alpha |V|$. We complete the proof by substituting $S= V\setminus V_t \ge (1-\alpha) n$ and $C= \lceil{\log_{(1-\delta)} \alpha}\rceil$.
\end{proof}

We remark that the above lemma has already been proved in~\cite{art:fps10} (in the hypergraph setting). A similar result has also been proved in~\cite{fm12} (in the bipartite matching setting) for $k\ge 8$.
With respect to an allocation graph recall that we denote the set of vertices furthest from $F$ by $R$. Also for an integer $s$, $N_s(R)$ denotes the set of vertices at distance at most $s$ from $R$. The next lemma states that the neighborhood of $R$ expands suitably with high probability. We remark that the estimate, for expansion factor, presented here is not the best possible but nevertheless suffices for our analysis.
\begin{lemma}\label{lem:expan}
For any fixed $\varepsilon>0$, let $m=(1-\varepsilon) c_k^* n$ items are assigned to $n$ locations using $k$ random choices for each item and $G=(V,E)$ be the corresponding allocation graph. Then for any $0<\alpha < {1\over k-1}$ and every integer $s$ such that $1\le | N_{s}(R)|\le \alpha n$,  there exists a constant $\zeta>0$ such that $G$  satisfies the following with probability $1-n^{-\zeta}$.

\[
	|N_{s}(R) | >  \left( k-1- {\log e^{k}(k-1) \over \log{1\over \alpha(k-1)}}\right)  | N_{s-1}(R)| . \]

\end{lemma}
\begin{proof}
Recall that in the allocation graph $G$,  $R$ is the set of vertices furthest from the set of free vertices. The set of vertices at distance at most $s$ from $R$ is denoted by $N_{s}(R)$. Note that each occupied vertex in $G$ holds one item. By construction of the allocation graph $N_{s}(R)$ is the set of vertices representing the choices of items placed on vertices in $N_{s-1}(R)$. In the hypergraph setting where each item corresponds to an edge, $|N_{s}(R)|$ is the number of vertices spanned by the set of edges of size  $|N_{s-1}(R)|$. We can now use Lemma~\ref{lem:expanhyper} to obtain the desired result.
\end{proof}
We define $\mu: =   {\log e^{k}(k-1)/ \log {(- \alpha(k-1))}} .$ For some fixed $\gamma >0$ we set
\begin{equation} \label{eq:alpha}
\alpha := \exp\left({-k\over k-2-\gamma}\right) (k-1)^{-1- {-1\over k-2-\gamma}},
\end{equation}
which implies that $\mu = k-2-\gamma$.

The following corollary follows from the above two lemmas.
\begin{corollary} \label{cor:maxLabel}
With high probability, the maximum label of any vertex in the allocation graph is $O(\log n)$.
\end{corollary}
\begin{proof}
Set $\alpha$ as in \eqref{eq:alpha}.
  Let $d$ be the shortest distance of vertices in $R$ to $S$. Then by Lemma~\ref{lem:expan}  with high probability,
    \begin{align*}
   |N_{d}(R) | >  &\left( k-1- {\log e^{k}(k-1) \over \log{1\over \alpha(k-1)}}\right)  | N_{d-1}(R)|  = (1+\gamma)^d  |R|,
  \end{align*}
which implies that $d< \log_{1+\gamma} \alpha n $.
Note that the shortest distance of vertices in $S$ to $F$ is a constant $C(\alpha,\delta)$ for $\delta$ defined in Lemma~\ref{lem:dist}. Moreover, by Proposition~\ref{prop:lev} the label of any vertex is upper bounded by its distance to the set of free vertices. Therefore, the label of any vertex $v$ is such that $L(v) = O( \log_{1+\gamma} \alpha n)$.
\end{proof}
We now prove our main theorem.
\vspace{-4pt}
\begin{proof}[Proof of Theorem~\ref{thm:main}]
Set $\alpha$ as in \eqref{eq:alpha}.
Then by Lemma~\ref{lem:dist}, with probability $1-O(1/n)$, there exists a $C=C(\alpha, \varepsilon)$ and a set $S$  such that $|S| \ge (1-\alpha)n$ and every vertex $v\in S$ satisfies $d(v,F)\le C.$
Let $T+1$ be the maximum of the distances of vertices in $R$ to $S$, i.e.,
\[ T = \max_{v \in R} d(v,S) -1 .\]
Clearly the number of vertices at distance at most $T$ from $R$ is at most $\alpha n$, i.e., $|N_T(R)|\le \alpha n$.
Moreover for all $t<T$, $|N_t(R)| < |N_T(R)|$.
Then by Lemma~\ref{lem:expan}, for all $t\le T$ the following holds with high probability,
\[ |N_{t+1}(R)| >  \left(k-1- \delta\right)| N_t(R)|.\]
One can check that for $\gamma >0$ and $\alpha$ as chosen above, $ \delta < k-2-\gamma.$
The total distance of all vertices from $F$ is then given by
 \[D=  \sum_{v\in N_{T}(R)} d(v,F) + \sum_{v\in S} d(v,F). \]
 As every vertex in $S$ is at a constant distance from $F$,  we obtain $\sum_{v\in S} d(v,F)=O(n)$.
 Note that for every $i>0$, $ | N_{i}(R)| - | N_{i-1}(R)|$ is the number of vertices at distance $i$ from $R$.
Therefore,
 \begin{align*}
 &\sum_{v\in N_{T}(R)} d(v,F)=  (T+C)|N_{0}(R)| + \sum _{i=1}^{T} (T+C-i)(| N_{i}(R)| - | N_{i-1}(R)|)\\
 &=(T+C)|N_{0}(R)| + \sum _{i=1}^{T} (T-i)(| N_{i}(R)| - | N_{i-1}(R)|) +C \sum _{i=1}^{T}( | N_{i}(R)| - | N_{i-1}(R)|)\\
 &=(T+C)|N_{0}(R)| + \sum _{i=1}^{T} (T-i)(| N_{i}(R)| - | N_{i-1}(R)|) +C ( | N_{T}(R)| - | N_{0}(R)|)\\
 &= \sum _{i=1}^{T} \bigg((T-i)(| N_{i}(R)| - | N_{i-1}(R)|) +|N_0(R)|\bigg)+C \cdot | N_{T}(R)| =\sum _{i=0}^{T-1} |N_i(R)| + O(n).
 \end{align*}
Now with high probability, we have $|N_{T-j}(R) | <    {| N_{T}(R)| \over (k-1-\delta)^j } .
$
Therefore,
\[
\sum _{i=0}^{T-1}| N_i(R)) |< |N_{T}(R)|  \sum_{j=1}^{T}   {1 \over (k-1-\delta)^j }  <  |N_{T}(R)|  \sum_{j=1}^{T}   {1 \over (1+\gamma)^j } =O(n),\]
which completes the first part of the proof of Theorem \ref{thm:main}.
To bound the expected time, we observe that for $i$ such that $|N_i(R))|< n^{1/2}$ combining with the fact that for any $i$, $|N_i(R)|< |N_{i-1}(R)|$  the following holds
$$\sum_{i}|N_i(R)|< \sum_{j=1}^{n^{1/2}}j = n^{1/2}\cdot {(n^{1/2} +1) \over 2}= O(n)$$
with probability $1$.

For all other $i$ using lemmas~\ref{lem:expanhyper} and \ref{lem:expan}
$$\sum_{i}|N_i(R)| < |N_{T}(R)|  \sum_i {1 \over (k-1-\delta)^i} < n $$ with probability $1-e^{-O(n^{0.5})}$.
Note that we already proved that the maximum value of the sum of all the labels can be atmost $n^2$ (see discussion after Lemma~\ref{lem:graph}). This implies that for such $i$
$$E\left(\sum_{i}|N_i(R)|\right) < n (1-o(1)) + n^2 e^{-O(n^{0.5})} = O(n)$$

\end{proof}
We obtain the following corollary about maximum matchings in left regular random bipartite graphs. Recall that a bipartite graph $G=(L\cup R;E)$ is  $k$-left regular if each vertex $v\in L$ has exactly $k$ neighbors in $R$.

\begin{corollary}
For $k\ge 3$ and $c^*_{k}$ as defined in Theorem~\ref{thm:mainO}, let $G=(L\cup R;E)$ be a random $k$-left regular bipartite graph such that ${|L| / |R| }<c^*_{k}$.  The local search allocation method obtains a maximum cardinality matching in $G$ in time $O(|R|)$ with probability $1-o(1)$.
\end{corollary}
\begin{proof}
We assign label $0$ to each of the vertices in $R$ initially. Each vertex in $L$ can be considered as an item and let $R$ be the set of locations. The $k$ random choices for $v\in L$ (item) are the $k$ random neighbors of $v$. We can now find a matching for each $v\in L$ by using Algorithm~\ref{algo:orientEdge}.
\end{proof}

\input{experiments}

\section{Conclusions and Outlook}
\label{chap:conc}

In this article, we proposed and analysed an insertion algorithm, the \emph{Local Search Allocation} algorithm, for cuckoo hashing that runs in linear time with high probability and in expectation. Our algorithm, unlike existing random walk based insertion methods, always terminates and finds an assignment (with probability 1) whenever it exists. We also obtained a linear time algorithm for finding perfect matchings in a general large bipartite graphs.

We conducted extensive experiments to validate our theoretical findings and report an order of magnitude improvement in the number of moves required for allocations as compared to the random walk based insertion approach. Secondly, we considered a real world social bookmarking graph dataset to evaluate the performance of our bipartite graph matching algorithm. We observe an order of magnitude improvement when the maximum allowable number of moves is set to $n$, but more interestingly we observe that the optimal solution is already reached at a small allowable limit of $5$ with a substantial performance improvement of almost three orders of magnitude over Hopcroft-Karp algorithm.

It should be noted that although the space complexity for label maintenance is $O(n)$, the number of bits required to encode each label is logarithmic in the maximum allowable moves. This allows compact representations of these labels in memory even without using integer encoding schemes that might further improve memory footprints while storing small integer ranges.

In the future we would like to consider other generalized variants of graph matching problems using such a label propagtion scheme. Also interesting to investigate is the impact of graph properties like diameter, clustering coefficients etc. on the only parameter in our algorithm, i.e., maximum allowable moves. This would go a long way in automatic parameterization of LSA.

\section{Experiments}

In this section we discuss the performance of our proposed LSA algorithm on randomly generated instances with density less than the threshold and then on real-world large datasets with arbitrary densities.
 The rationale of our evaluation is two-fold. First, we establish the effectiveness of LSA for randomly generated instances with densities close to the threshold in terms of abstract cost measures and compare it with the state of the art method employed for Cuckoo Hashing for a large number of randomly generated instances. Second, we would want to validate the performance of LSA in terms of wall-clock times on large real-world bipartite graphs with arbitrary densities and structure ( i.e. these are not necessarily left regular bipartite graphs).

\subsection{Performance on Random Graphs}

We present some simulations to compare the performance of local search allocation with the random walk method which (to the best of our knowledge) is currently the state-of-art method and so far considered to be the fastest algorithm for the case $k\ge 3$. We recall that in the random walk method we choose a location at random from among the $k$ possible locations to place the item. If the location is not free, the previous item is moved out.  The moved out item again chooses a random location from among its choices and the procedure goes on till an empty location is found. In our experiments we consider $n\in [10^5, 5\times 10^6]$ locations and $\lfloor cn \rfloor$ items. The $k$ random locations are chosen when the item appears. All random numbers in our simulations are generated by \emph{MT19937} generator of GNU Scientific Library~\cite{gnu}.

Recall that a move is either placing an item at a free location or replacing it with other item.
In Figure~\ref{fig:1} we give a comparison of the total number of moves (averaged over $100$ random instances) performed by local search and random walk methods for $k=3$ and $k=4$. Figure~\ref{fig:2} compares the maximum number of moves (averaged over $100$ random instances) for a single insertion performed by local search and random walk methods. Figure~\ref{fig:3} shows a comparison when the number of items are fixed and density (ratio of number of items to that of locations) approaches the threshold density. Note that the time required to obtain an allocation by random walk or local search methods is directly proportional to the number of moves performed.
\begin{figure*}[h!]
   \centering
     \subfigure[$k=3$, $c=0.90 ~(c^*_3\approx 0.917)$]{\label{fig:total}\includegraphics[width=0.45\textwidth]{total-3.pdf}}
   \quad
     \subfigure[$k=4$, $c=0.97 ~(c^*_4\approx 0.976)$] {\label{fig:all-3}\includegraphics[width=0.45\textwidth]{total-4.pdf}}
     \vspace{-8pt}
   \caption{Comparison of total number of moves performed by local search and random walk methods.}
   \label{fig:1}
\end{figure*}
\begin{figure*}[h!]
   \centering
    \subfigure[ $k=3$, $c=0.90 ~(c^*_3\approx 0.917)$.]{\label{fig:max}\includegraphics[width=0.45\textwidth]{max-3.pdf}}
   \quad
 \subfigure[$k=4$, $c=0.97 ~(c^*_4\approx 0.976)$.]{\label{fig:his to-3}\includegraphics[width=0.45\textwidth]{max-4.pdf}}
   \vspace{-8pt}
   \caption{Comparison of maximum number of moves performed by local search and random walk methods}
    \label{fig:2}
\end{figure*}
\begin{figure*}[h!]
   \centering
     \subfigure[$k=3$, $c\le 0.915 ~(c^*_3\approx 0.917)$]{\label{fig:fix-3}\includegraphics[width=0.45\textwidth]{totald-3.pdf}}
   \quad
       \subfigure[$k=3$, $c\le0.915 ~(c^*_3\approx 0.917)$] {\label{fig:fix-3-total}\includegraphics[width=0.45\textwidth]{maxd-3.pdf}}
       \vspace{-8pt}
   \caption{ Comparison of total number of moves and maximum number of moves (for fixed number of locations, $n=10^5$) performed by local search and random walk methods when density c approaches $c^*_k$.}
      \vspace{-1pt}
   \label{fig:3}
\end{figure*}
\begin{figure}[h!]
   \centering
    \includegraphics[width=0.85\textwidth]{totalGen-3-2.pdf}
    \caption{Total number of moves for the case where bin capacities (maximum load, $s$) is greater than 1.}
    \label{fig:totalGen}
    \end{figure}

\begin{algorithm}[h!]
\caption{AssignItem ($x, \mathbf{L},\mathbf{T}$)}
\label{algo:orientEdgegen}
\begin{algorithmic}[1]
\STATE Choose an item $v$ among the $k$ choices of $x$ with minimum label $L(v)$.
\keyword{if}{$(L(v)>=n-1)$ }
\STATE $\mathbf{EXIT}$  ~~~~~~~~~~~~~~~~~~~~~~~ $\rhd${\textbf{Allocation does not exist}}
\keyword{else}
\keyword{if}{$({\textsc{Items}}(v)> s-1)$ }
\STATE $L(v) \leftarrow 1+ \min{(L(u)| u \neq v \text{~and $u \in x$})}$
\ENDIF
\keyword{if}{$(\textsc{Items}(v)==s )$}
\STATE Choose an item (call it b) randomly from the $s$ items in v
\STATE $y\leftarrow b$~~~~~~~~~~~~~~~~~~ $\rhd${\textbf{Move that replaces an item}}
\STATE Place $x$ in $v$
\STATE $\mathbf{CALL}$ {AssignItem($y, \mathbf{L},\mathbf{T}$)}
\keyword{else}
\STATE Place $x$ in $v$ ~~~~~~~~~~~~~~~~~~ $\rhd${\textbf{Move that places an item}}
\ENDIF
\ENDIF
\end{algorithmic}
\end{algorithm}
We also consider the case when each location can hold more than one item. To adapt LSA for this setting we make a small change, i.e., the label of a vertex (location) stays 0 until it is fully filled. Algorithm~\ref{algo:orientEdgegen} gives the modified procedure for the general location capacities. Here {\sc{Items}}$(v)$ gives the number of items already placed in $v$. Let the location capacity or maximum load allowed be $s$. Figure~\ref{fig:totalGen} suggests that the total number of moves are linear in the number of locations for the cases $k=3,4$ where the maximum location capacity is greater than $1$.

We remark that local search allocation has some additional cost, i.e., the extra space required to store the labels. Though this space is $O(n)$, local search allocation is still useful for the applications where the size of objects (representing the items) to be allocated is much larger than the labels which are integers. Moreover, with high probability, the maximum label of any vertex is $O(\log n)$. Many integer compression methods~\cite{inp:sgl10} have been proposed for compressing small integers and can be potentially useful in our setting for further optimizations. Also in most of the load balancing problems, the speed of finding an assignment is a much desired and the most important requirement.

\begin{table*}[ht!]
\centering
\footnotesize
\begin{tabular}{@{}l l l l @{}}
\toprule
\multicolumn{1}{l}{} & Maximum Number of Moves                  & Wall-clock times     & Result Size  \\
\hline \noalign{\smallskip}
LSA        &   1      & 12    & 1,029,449  \\
       &   2      & 12    & 1,080,006  \\
        &   4      & 12    & 1,082,199  \\
        &   5      & 16    & 1,082,214  \\
        &   10      & 15    & 1,082,214  \\
        &   50     & 15    & 1,082,214  \\
        &   100     & 15    & 1,082,214  \\
        &   1000     & 15    & 1,082,214  \\
        &   10,000    & 27    & 1,082,214  \\
        &   100,000    & 136    & 1,082,214  \\
        &   $n$    & 1,887    & 1,082,214  \\
\midrule

Hopcroft-Karp                &  & 12,605 & 1,082,214 \\

\hline \noalign{\smallskip}
\end{tabular}
\caption{Performance of LSA on \textsf{Delicious} dataset. Time is measured in seconds.}
\label{table:softlabel}
\end{table*}

\subsection{Performance on Real-world graphs}

Next, we compare our runtime performance to the optimal algorithm proposed by Hopcroft et al.~\cite{hopcroft1973n}. In this experiment we want to study the effect of number of allowable moves on (a) the actual wall-clock times , (b) the result quality in terms of the size, or number of edges, of the final matching produced (refer Figure~\ref{table:softlabel}). We selected the following representative realworld dataset for our experiments:

\begin{itemize}
  \item \textsf{Delicious dataset :} The \textsf{Delicious} dataset spans nine years from 2003 to 2011 and contain about 340 mio. bookmarks, 119 mio. unique URLs, 15 mio. tags and 2 mio. users~\cite{zubiaga2013harnessing}. Each bookmarked URL is time stamped and tagged with word descriptors. The nodes in one of the sets are URLs and in the other are its corresponding bookmarks.

\end{itemize}

We first observe that the optimal result in the \textsf{Delicious} dataset, i.e. 1,082,214, is already obtained when the limit on the allowable moves is only 5. We are of course sure about the optimality of the procedure when the maximum allowable moves is set to $n$ and that already is 10x improvement over the time taken by Hopcroft-Karp algorithm. For lower allowable limits of 5 and 10 the performance improvements are almost 1000x. Interestingly, as we increase the limit on the allowable moves to place any item (match any edge), the runtime does not change showing that only a small of defections are sufficient to arrive at an optimal result. However, at higher limits, indeed other permutations are explored (in this case unsuccesfully) resulting in increased runtimes. The stopping creteria unlinke in case of perfect matchings cannot be predetermined in general. In future we plan to devise methodology to stop the algorithm when the maximum matching is retrieved. In any case when the limit is set to $n$, that would guarantee optimality, we still perform an order of magnitude faster than the optimal algorithm of Hopcroft-Karp.

redpajama_set_name: RedPajamaArXiv


text:
Home Expansions Downstream Valero and Diamond Green Diesel expansion completed
Valero and Diamond Green Diesel expansion completed
The Diamond Green Diesel expansion project at Valero's St. Charles refinery (DGD 2), which increases renewable diesel production capacity by 400 million gallons per year, was completed in the third quarter and is in the process of starting up.
"We are excited to report that the Diamond Green Diesel expansion project at Valero's St. Charles refinery was successfully completed on-budget and ahead of schedule," said Joseph W. Gorder, CEO, Valero. "This is a testament to the strength of our engineering and operations teams, who got this accomplished despite Hurricane Ida related challenges."
The new DGD plant at Valero's Port Arthur refinery (DGD 3), which is expected to have a renewable diesel production capacity of 470 million gallons per year, is progressing well and is still expected to commence operations in the first half of 2023, increasing DGD's total annual production capacity to approximately 1.2 billion gallons of renewable diesel and 50 million gallons of renewable naphtha.
The large-scale carbon sequestration project with BlackRock and Navigator is also progressing on schedule. Navigator has received the necessary board approvals to proceed with the carbon capture pipeline system as a result of a successful binding open season. Valero is expected to be the anchor shipper with eight of Valero's ethanol plants connected to this system, producing a lower carbon intensity ethanol product to be marketed in low-carbon fuel markets that is expected to result in a higher product margin.
Refinery optimization projects that are expected to reduce cost and improve margin capture are progressing on schedule. The Pembroke Cogeneration Unit, which is expected to provide an efficient and reliable source of electricity and steam, was completed and commissioned in the third quarter of 2021. The Port Arthur Coker project, which is expected to increase the refinery's utilization rate and improve turnaround efficiency, is still expected to be completed in 2023.
Capital investments attributable to Valero are forecasted to be $2.0 billion in 2021, of which approximately 60 percent is for sustaining the business and approximately 40 percent is for growth projects. Over 60 percent of Valero's 2021 growth capital is allocated to expanding the renewable diesel business.
Downstream Valero Energy Diamond Green Diesel Expansion Top News

redpajama_set_name: RedPajamaCommonCrawl


Strike the right balance between sweet and salty. Make your life sweeter by adding healthier forms of sugar and poise the rest by adding a little zing with various varieties of salts! Buy best organic sugar, brown sugar, white sugar, refined sugar, coconut and palm sugar, organic jaggery, organic jaggery powder. Himalayan salt, pink salt and much more online in India only from Wellnessmonk at huge discounts!


text:
Jammu and Kashmir activist Rita Jetinder dies during Live TV show
Jammu and Kashmir activist Rita…
Hurriyat (G) welcomes return of…
Former aircraftman donates 1.08 crore…
Mumbai building collapse LIVE updates:…
A renowned Jammu and Kashmir (J&K) social activist Rita Jetinder died during a TV show after she suffered a cardiac arrest on Monday. A prominent Jammu and Kashmir scholar Rita Jetinder, who was on a Doordarshan LIVE chat show suffered a cardiac arrest when she was presenting her views during the show.
NewsX Bureau
10 September 2018,
Social activist Rita Jetinder dies during LIVE TV show
A renowned Jammu and Kashmir (J&K) social activist Rita Jetinder died during a TV show after she suffered a cardiac arrest on Monday. A prominent scholar Rita Jetinder, who was on a Doordarshan LIVE chat show suffered a cardiac arrest when she was presenting her views during the show. According to a 56-second video clip which has gone viral on social media, Rita Jetinder was presenting her views on some topic when she suddenly collapsed and died during the show. She was sitting not very far from the host.
A prominent activist Rita Jetinder was also the secretary of Jammu and Kashmir Academy of Art, Culture and Languages. Several people expressed their condolence on the sudden demise of activist Rita Jetinder. According to the video clip which is being circulated on social media, moments before the activist suffered a cardiac arrest, she was presenting her views during the DD Kashmir morning show and looking all fine.
Also Read: Congress says Modi looting people's money for own publicity
However, while speaking in the show, she suddenly took a pause and gave some weird expression and suddenly leaned down backwards with her mouth opened. Looking at this, other speakers present on the show at first did not get what happened to the activist following which video ends.
Also Read: Nirbhaya rape case: NCW sends notice to Tihar Jail over pending execution of convicts
The state of Jammu and Kashmir is witnessing several discussions on the Article 35A which ensures special rights to the people of the state. Meanwhile, regional political parties including the National Conference (NC) and Peoples' Democratic Party (PDP) have already stated that they will boycott the urban body and civic body elections scheduled to be held later this year until the Centre ensures that there will be no alteration to Article 35A.
For all the latest National News, download NewsX App


The 18-year-old made his debut for the club earlier in the season, scoring against Burton Albion, and appeared from the start for the first time at Sheffield Wednesday in midweek.
In what is a breakthrough season for the academy graduate, he was over the moon to get the call up from manager Martin O'Neill.
He said: "I was nervous at the time but also excited as I wanted to show everyone what I could do. The nerves started to kick in when we were in the tunnel, then shaking the players hands but after I got my first touch I got into it. The players around me helped me a lot. I was speaking to Robbo a lot, Jack Colback helped me during the game as well so it was great to have that support around me.
"The gaffer told me to be myself; sometimes you are going to lose the ball but be positive and keep working hard. That was the thing and I just had to have that strong mentality to keep going, not crumble or anything and have the confidence to beat my man. I enjoyed it in the first half as you could see.
"Overall, considering it was my first start, I thought I did well. It was hard because I am an attacking player but in the Championship you have to do a lot of work to help your teammates out. I thought I did my defensive duties well and attacking, we probably didn't have as much of the ball as we would have liked but overall I thought I did okay but there is more to come."
Following on from his debut in the Carabao Cup, Appiah went on to make his league debut against Leeds United at The City Ground in January and has since gone on to represent England Under 19s for the first time. He is determined to keep impressing and hopes to be involved again this weekend.
He said: "It has been a tough season but also been a good one for me. I made my debut, scored on my debut and have been able to get some minutes. I just want to take every game as it comes, work hard for the gaffer and on the training pitch and when I do get a chance, I want to show what I am capable of.
"I've just got to keep working, listening to the coaches and all of the experienced players and hopefully I could be starting again or on the bench.
"It would be amazing, I would love to start 100 per cent. I want to show the Forest fans what I am about. Hopefully I can get on the pitch, excite the crowd and take my chance."
Arvin was speaking with Forest Review for this Saturday's game at The City Ground and you can read the full interview in the matchday programme, available for £3 from around the ground before the match.
There is one final Forest Review on sale this season for the last home game against Bristol City this afternoon.
Make sure you pick up tonight's copy of Forest Review for the Sky Bet Championship clash between Nottingham Forest and Sheffield Wednesday at The City Ground.
Make sure you pick up a copy of Forest Review ahead of today's Sky Bet Championship clash with Birmingham City.


text:
Q: ant classpath cannot find wsdl2java i defined an ant task like this:
<taskdef name="WSDL2JavaTask" classpath="/opt/IBM/WebSphere/AppServer/lib/*.jar" classname="com.ibm.websphere.ant.tasks.WSDL2Java" />

But i am getting:
taskdef class com.ibm.websphere.ant.tasks.WSDL2Java cannot be found
 using the classloader AntClassLoader[/opt/IBM/WebSphere/AppServer/lib/*.jar]

i searched online to see which jar file has the wsdl2java class but i am not able to find it. some sources say it is webservices.jar but there is no such jar in the websphere default lib directory.

redpajama_set_name: RedPajamaStackExchange


text:
Calorimetric and Raman investigation of cow's milk lactoferrin
Lactoferrin (LF), a non-heme iron-binding protein of blood plasma and milk with antioxidant, cariostatic, anticarcinogenic, and anti-inflammatory properties, has been studied by differential scanning calorimetry (DSC) and Raman spectroscopy over a wide pH range (4.0–9.0). Using these two techniques, the modifications in the quantity of iron bounded in the cow's milk LF and in the secondary structures, as a function of pH and heating, have been evaluated. DSC curves showed higher value of denaturation temperatures and enthalpy changes when LF was saturated with iron (holo-form) than when it was in its unsaturated form (apo-form). The denaturation curves of the protein solutions at pH ≥ 5.5 confirming that LF is a mix of apo- and holo-forms; on the contrary at pH 4.0, the holo-form is practically absent. Spectroscopic investigation showed that, as a function of pH, the content of α-helix increases up to pH 7.4, followed by a small decrease by further pH increase. The β-sheet percentage exhibits the opposite behavior, while the random-coil and turn structures do not change noticeably. In contrast, after heat-induced denaturation, strong variations were observed in the secondary structure, with an evident increase of β-sheet and decrease of the α-helix percentage. Finally, both thermal and spectroscopic analysis pointed out that the structure of cow's milk LF is strictly sensible to pH variation and it has the highest thermal stability at physiological pH.
Titolo: Calorimetric and Raman investigation of cow's milk lactoferrin
Autore/i: IAFISCO, MICHELE; FOLTRAN, ISMAELA; DI FOGGIA, MICHELE; BONORA, SERGIO; ROVERI, NORBERTO
IAFISCO, MICHELE
FOLTRAN, ISMAELA
DI FOGGIA, MICHELE
BONORA, SERGIO
ROVERI, NORBERTO
Digital Object Identifier (DOI): http://dx.doi.org/10.1007/s10973-010-1084-2
Abstract: Lactoferrin (LF), a non-heme iron-binding protein of blood plasma and milk with antioxidant, cariostatic, anticarcinogenic, and anti-inflammatory properties, has been studied by differential scanning calorimetry (DSC) and Raman spectroscopy over a wide pH range (4.0–9.0). Using these two techniques, the modifications in the quantity of iron bounded in the cow's milk LF and in the secondary structures, as a function of pH and heating, have been evaluated. DSC curves showed higher value of denaturation temperatures and enthalpy changes when LF was saturated with iron (holo-form) than when it was in its unsaturated form (apo-form). The denaturation curves of the protein solutions at pH ≥ 5.5 confirming that LF is a mix of apo- and holo-forms; on the contrary at pH 4.0, the holo-form is practically absent. Spectroscopic investigation showed that, as a function of pH, the content of α-helix increases up to pH 7.4, followed by a small decrease by further pH increase. The β-sheet percentage exhibits the opposite behavior, while the random-coil and turn structures do not change noticeably. In contrast, after heat-induced denaturation, strong variations were observed in the secondary structure, with an evident increase of β-sheet and decrease of the α-helix percentage. Finally, both thermal and spectroscopic analysis pointed out that the structure of cow's milk LF is strictly sensible to pH variation and it has the highest thermal stability at physiological pH.


Working together to prevent child abuse.
In honor of National Child Abuse Prevention Month, Children's Home of Northern Kentucky (CHNK) is partnering with Izzy's Restaurant throughout the month of April to promote the importance of communities – and businesses within those communities – working together to prevent child abuse.
Through the end of the month, Izzy's customers can purchase a blue paper ribbon for a $1 donation in support of Children's Home of Northern Kentucky. Ribbons will be posted in each of Izzy's nine restaurants for the duration of April, providing a visual cue that child abuse prevention is a community issue, and that every member of the community can be a part of raising awareness and sharing strategies for prevention.
Customers dining in at each Izzy's restaurant will also notice table tents promoting CHNK's behavioral health and substance use treatment programs for adolescents, as well as opportunities for joining the fight against child abuse. In addition to being able to purchase a blue ribbon in-store, customers can text 33923 to make a donation to CHNK straight from their smartphones.


text:
Mausolus First Ascent
Ryan Valentine
Approximate routeline of "Mausoleum" which Helander and Vincik climbed over 40 hours. It was the first ascent of Mt. Mausolus. [Photo] Clint Helander
Anchorage local Clint Helander and his partner Scotty Vincik took advantage of near perfect late winter conditions to claim the first ascent of Mt. Mausolus (9,170') in Alaska's Revelation Mountains. Located in the southwest corner of the Alaska Range, the Revelations are a somewhat obscure pocket of steep granite peaks. Helander first heard of the Revelations in 2006 and had been dreaming of them ever since.
Vincik leading on the ribbon of ice. [Photo] Clint Helander
In 2007, after receiving the American Alpine Club's Mountain Fellowship Grant, Helander and long time climbing partner Seth Holden set their sights on the steep, unclimbed west face of Mt. Mausolus. Repeated trips to the Revelations over the course of the next two years led to other first ascents in the range but attempts to even reach the base of Mausolus remained unsuccessful. In 2010, aware that the season was too warm for good climbing conditions, the pair reconnoitered the first 2,000 feet of the route in anticipation of coming back the following season to complete their now four-year goal of reaching the summit.
Unfortunately, in August of 2010 Seth Holden was killed in a place crash, making it the last time the pair would attempt Mausolus together. With the fear that more climbers were starting to focus on the Revelations and Mt. Mausolus in particular, Helander returned with Scotty Vincik on March 15 of this year, carrying the ashes of his friend. Unlike the previous winter, a month of high pressure systems described by Helander as "a skier's nightmare and an alpine climber's dream" gave the pair very little snow and an almost continuous ribbon of ice down the west face. Packing three days of food, sleeping bags, a double set of cams and a limited number of ice screws the pair took advantage of the pristine conditions and used the first day to move through perfect WI4 and WI5 climbing to a precarious bivy. Safe from rockfall though anything but comfortable, the pair spent the night roughly 1,200 feet from their goal. The next day they tackled long runout pitches of steep WI5 climbing which gradually eased into less difficult terrain above and finished with a 400-f00t, unprotected simul-climb up steep snow to the summit just as the light began to fade.
After taking a moment to scatter the ashes of the friend who had started this four-year dream, Helander and Vincik rappelled down to the previous night's bivy to retrieve their sleeping bags and other gear. Continuing down the mountain in the dark, they finally reached a snow cave to complete their nearly 40-hour push. Helander and Holden had previously discussed naming the route "The Mausoleum," should they ever reach the summit. With Holden's ashes spread across the summit, it gave new meaning to the name.
Mausolus with the route climbed by Helander and Vincik just visible. [Photo] Cliff Cochran
Source: Clint Helander
Helander's photos from the climb may be viewed here.
Oberlatz
I've walked past Mausolus from both the east and west sides. The only words that come to mind for this well-earned ascent are "Holy shit!" Solid effort Clint and Scotty! HUGE. You have reason to be proud.
srourke
Clint, Yes we climbed from the Stoney glacier so I guess I'm getting it wrong. I was with Jim F. and Mike Wood (not the alaska Mike). Your picture looked so much like the face we climbed...I'll break out my slides and check it out. Looking at your picture, I just thought we went right where your stripe of ice went straight up.
Our base camp was on a pocket glacier off Sled Pass I think. We had wanted to land on the Stoney glacier but it was too stoney so Paul Roderick and Dave Lee ? landed us near what I think is Sled Pass and we skiied and hiked over to what must be the East face. Our Cache by the e. face got raided by a bear before our attempt but it only bit into a water bottle. The bears were using the Stoney glacier as a short-cut between valleys. We spent days looking at the gully system we climbed and didn't see any rock or ice fall so we went for it. The day we climbed got much warmer than the days before and huge snow mushrooms began detaching from the steep walls on the side and flying over our heads. Also, slush avalanches began coming down too. They looked like whitewater. We kept going to the safety of the ridge which we reached at a distinct notch. A rock pitch out of the notch put us on a nice ledge in some small gendarmes where we were finally safe.
You guys obviously got it right by climbing in colder, icier conditions. We were a bit too agressive and got really lucky. My hat is off to you guys.
Clint Helander
Hello Scott, did you attempt the west face from the Swift Glacier or the east face from the Stony Glacier? Did you attempt it with James Funsten? I was only aware of an attempt from the east (James Funsten). Either way, that is very, very cool. What a close call! Please tell us more. What happened that day?
We did not come across ANY sign of anyone on the mountain. In fact, we didn't even ever hit a ridge. We went up the most direct route on the west face (from the Swift Glacier) to the summit pyramid to the summit. I certainly thought of just how close the previous party had come to topping out. What a bummer!
I can't say enough about our luck and the conditions we had! It was truly an experience of a lifetime and I will forever cherish the time spent on the summit. The views were amazing, the feeling was euphoric and luckily Scotty was tired and uncaffeinated so he didn't talk TOO much!!! A dream lived!
AlpineEssence
Nice work booooyyz!
scotty vincik
I'd like to convey the delightful feeling of finding such climable and safe conditins on this route. Everything was straightforward; strenuous because of the unrelenting steepness, length, and wicked hardness of the deep frozen seasonal ice, but the route passed by with comparative ease by Alaskan norms. We were runout only due to the lack of ice screws, hungry only because I took only bagels and bars for food. We mananged to spend the night without shivering, despite sleeping in slings. The ice was grey, and bonded. It was quite a different experience from chimneying up curtains of welded sugar snow, which so often are found in Alaska. The summit was cold, with deadly still air, and views far out into the reaches of western Alaska, an area incomparable in vastness within the U.S. It was alpine climbing as you dream of, and our primary feeling about the route was one of luck and gratitude for our perseverance exploring up here. This one is for the monkeys, and the monkeys who have passed. Scotty
that and it's an an elegant line.
Apcolapyse next?
I think the most impressive part of this ascent, is the fact that it was done in winter.
Nice job!!! Mausolus is an amazing looking peak. We tried this line in June 1998 and gained the ridge but did not make it over to the summit. The conditions were horrendous (way too warm that day) and when we gained the ridge we just sat and counted ourselves very lucky to have survived the day. We carried no bivy gear and our time from the Stony glacier to the ridge and back was about 24 hours. We had some huge stuff fly by us that day and once we got committed we decided it would be safer to go up. Did you see any of our rap anchors from the ridge? I will always regret not bagging the top of this beautiful beast but am happy that we all made it back unscathed.
This was my first and only trip to Alaska and I will never forget our view of the Peak as we flew in. It just looked so impressive. As far as I know, it had never been attempted before we got there. Again, nice job!!!
Scott Rourke


Everything About The Toa Has Been Evaluated From A Functional And Weight-Saving Perspective. From The Durable And Breathable Synthetic Upper, To The Rubberized Foam Midsole And The Vibram Megagrip Outsole Lugs, All Elements Are Technically Solid And Efficiently Lightweight. And The Cushioned Running Shoe Feel Is Further Enhanced By An Event Waterproof Bootie To Keep Your Feet Dry And Comfortable.


text:
About IATUR vzw
Executive and council
JTUR
approved 31 July 2014
Glossary of terms in correspondence with Belgian Statutes of IATUR vzw
VZW - Vereniging Zonder Winst
Council - Raad van Bestuur
Executive Committee - Directiecomité
General Assembly - Algemene Vergadering
Current members - Toegetreden leden (individual members whose dues are current)
Active members - Werkelijke leden (those Current Members who manage the institutional operation of the Association, as well as the Vrije Universiteit Brussel, who fulfil the requirement under Belgian vzw law to have an Active Member outside the Council)
Institutional member - Institutionele leden
IATUR members - IATUR leden (includes active members, other current members, and institutional members)
1. Composition of the Members of the IATUR vzw Council and Executive Committee
The IATUR vzw governing Council consist of the following Office Bearers, all of whom must be and remain Active Members of the Association during the period that they hold their office
The Vice-President (one of two)
The Vice-President (two of two)
The Treasurer
Eight Council Members, one from each of the following geographic regions
North and East Asia
South Asia and Middle East
For daily affairs, an Executive Committee is formed by the following members:
The President, the Vice-presidents (two), the Secretary and the Treasurer
Appointed Advisors to the Executive, drawn from the current membership, whose mandate runs in parallel with the election cycle of the Executive and Council members at the time of appointment
The Executive can co-opt from up to two additional Advisors-at-Large from the current members for a period of up to one year
Members of the Council representing geographic regions may invite additional persons whose particular expertise would be of value to items under discussion at a meeting of the Council to attend these meetings as non-voting participants. Appointed Advisors and Advisors-at-Large also are non-voting participants at Executive and Council meetings.
2. Roles of the Members of the IATUR vzw Council and Executive Committee
(a) The President has responsibility for:
Overall management of the Association
Representing the Association at international meetings and with local, regional and international media
Chairing executive committee and general meetings
Working with the Treasurer to raise funds for the association
(b) The two Vice-Presidents have responsibility for:
Assisting the President in the overall management and promotion of the Association
Liaising with national statistical and international governmental organisations
Chairing executive committee and general meetings if the President is not available
Identifying policy applications using time use data
Assisting the Managing Editor of the Journal
(c) The Secretary has responsibility for:
Organising Executive Committee meetings, Council Meetings, Annual General Meetings and Special General Meetings
Managing organisational guidelines
Participating in the organisation of all IATUR vzw conferences and events
Managing the IATUR vzw archives
Informing the time use community of publications, data, events, resources, and organisational matters
Managing the website in conjunction with the Treasurer
Managing the membership and institutional affairs in conjunction with the Treasurer
(d) The Treasurer has responsibility for:
Collecting dues, managing accounts and other funds of the Association
Arranging audits
Working with the President to raise funding for the Association
Managing the website in conjunction with the Secretary
Managing the membership and institutional affairs in conjunction with the Secretary
(e) All Members of the Executive Committee shall have responsibility for:
Regularly participating in IATUR events
Co-ordinating ethical standards in the field
Promoting IATUR vzw and time use surveys to agencies which might use or fund time-use surveys
Promoting high quality standards time use data collection, data harmonisation and analysis
Continuing members of the Executive mentor newly appointed or elected members of the Executive Committee
(f) Location of treasurer in relation to other members of the Executive Committee
The Treasurer and at least one Appointed Advisor should reside and work in the same country, preferably same jurisdiction within that country, as another member of the Executive so that more than one member of the Executive can sign for and have access to the accounts
(g) Transitions between post-holders on the Executive Committee and Council
All Active Members of the Executive Committee and Council are elected by the Current Membership at the General Assembly to hold posts for 4 year terms
While post-holders may be re-elected, any current member may put their name forward to stand as a candidate for any post in the approach of new electoral cycles
The Executive and Council reserve the right to review propositions from people who wish to stand as the candidates for the Executive Committee elected posts to ensure that these candidates have sufficient institutional support and experience to take on the post
Executive Committee and Council members who cannot serve through the end of their elected term normally should give at least six months notice in writing to the Secretary (or in the case of the Secretary, the Secretary shall give at least six months notice in writing to the President) in advance of the next annual general assembly to permit a call for elections
Executive Committee and Council members who do not keep their payment of IATUR membership dues up-to-date or otherwise fail to discharge their specified duties as post-holder will lose their Active Membership status and thus will not be able to vote on IATUR business decisions
Active Members will continue to discharge the duties of their posts through that elections and until after all functions reasonably can be turned over to the new post-holder, unless exceptional circumstances arise or in the event that a member is removed by a vote of the Active Members at the General Assembly
(h) Members of the Executive attend Council Meetings to
Report on work of the Executive
Answer questions and concerns raised by Council Members about the running of the Association
Offer input based on their expertise to items on Council Meeting agendas
(i) The Council Members representing geographic regions will
Monitor time-related research, data collection and related events in their region
Attend meetings of the Executive and Council
Periodically write region reports for the Time Pieces section of the eIJTUR
Promote activities of the Association within their region
Act as a check on the activities of the Executive
(j) The Appointed Advisor(s) the Executive
The Secretary and Treasurer, as other members of the Executive as needed, can appoint Associate Advisors to assist with the performance of day to day operations of the Association as well as up to two specific project Advisors-at-Large, aiming to reflect the diversity of the IATUR vzw community in appointments
The Secretary will put forward prospective names to the Council for approval before Associate Advisors or Advisors-at-Large are appointed
(k) Past-Presidents may attends Council Meetings to offer input based on their expertise.
(l) The Managing Editor of the Electronic International Journal of Time Use Research may attend Council Meetings to represent the interests of the journal.
(m) All members of the Council, including Advisors to the Executive, and Advisors-at-large, commit to attend at least one of every three conferences, and commit to participate in at least one of every two Executive and Council meetings (even if this participation is over Skype or related teleconferencing means).
3. IATUR vzw membership
The principal criterion of eligibility for membership (both individual or institutional membership) is an interest in the field of time use research. Membership is open to all persons/institutions willing to subscribe to the Statutes and pay annual dues and other fees as may be required.
IATUR makes a distinction between Active and Current membership. Active Members make the legally binding decisions on behalf of the Association. Active Members include the elected members of the Council, the Immediate Past President, the Managing Editor of the eIJTUR, and the institutional member the Vrije Universiteit Brussel. Both Active and Current members have the powers granted by the Statutes of the IATUR vzw.
All new members and members who have renewed after the regularisation period of 8 weeks from 1 January until 28 February each annual cycle, and individual lifetime members who have not expressed an interest in involvement with the Association General Assembly for any given year during the regularisation period, cannot hold Active Member status or seek election to a Council post unless special dispensation is extended to that member by the Executive Committee. People who and institutions which have paid in previous years who have not renewed their membership are not Current Members. Active Members, Current Members, former members, and other people participating in IATUR conferences can attend General Assembly meetings and express views on matters under discussion which the Active members will take into account when making decisions. In the event of a controversial issue with a close vote, only Current Members will be able to vote in General Assembly meetings, and only Active Members will be able to vote on operational matters and make legally binding decisions.
Belgian vzw law requires a minimum of 2/3rds of Active Members be present or represented by proxy during the General Assembly meetings for decisions to count as approved, Active and Current membership distinction enables IATUR can meet this threshold to function as a legal not-for-profit Association vzw under Belgian law.
Institutional members, with exception of the Vrije Universiteit Brussel (whose institutional membership is a requirement of the incorporation in Belgium), only can hold Current Membership. The Council decides which applicants can become an institutional member based on the following criteria:
Being a formal organisation or institution whose aims are compatible with Association objectives (the latter criteria of which is decided in a vote of the Council)
Having an active and reputable research program in the field of time-use
Having at least one current member who has participated in at least two IATUR-conferences during the last 5 years
The Vrije Universiteit Brussel hosts the IATUR vzw and provides some facilities for daily affairs (office space, telephone and internet facilities, administration, and related overheads). Until the Association winds down incorporation in Belgium, the Vrije Universiteit Brussel holds an Active institutional membership represented by a legal counsellor.
4. Membership dues and membership list
IATUR distinguishes Individual Current Members, Individual Lifetime Current Members and Institutional Current Members. Members or employees of an institutional member are not automatically Individual Current Member of IATUR vzw. Each individual wishing to be a member should apply as an individual member.
The Association has regular expenses in Euros, and UK pounds sterling. Expenses associated with conferences are payable in the relevant local currency.
The Executive will set the dues to account for global currency fluctuations. Changes to dues must be approved at the annual General Assembly before coming into effect for the next Association registration period.
(a) The current annual dues for an Individual Current Member are:
€50,00 Standard membership – 1 year
€25,00 Membership for students, people from developing and transition economies, and retired persons (or the equivalent) – 1 year
Persons who wish to qualify for a reduced membership fee should provide evidence of eligibility for this status. The Treasurer and Secretary decide which people are eligible for a reduced membership fee.
(b) The current annual fees for a Individual Lifetime Current Membership are:
€375,00 Lifetime membership for people aged 50-59 at time of payment
€150,00 Lifetime membership for people aged 60+ at time of payment
Each year, people with a Lifetime Individual Membership who potentially qualify as Active Member have to explicitly indicate via the IATUR website that they plan to participate in the annual Council meeting and General Assembly to be counted as an Active Member in Council meetings and the General Assembly. The lifetime membership stays granted until death or until a decision from the Council/General Assembly to expel this member.
(c) The current annual fees for an institutional membership fees are:
€500,00 Institutional membership – 1 year
The Vrije Universiteit Brussel is exempted from this institutional fee as long as it hosts IATUR vzw.
The Association's Membership List containing the name, current email address and current membership status of each member shall be maintained by the Secretary and the Treasurer. The membership list shall not be passed on to other agencies.
5. Discipline, suspension and expulsion of members
In the event of an incident associated with an IATUR vzw Current Member or any person working with time use data or associated with a time use study that brings the methodology or field into disrepute or poses challenges to the legitimacy or standing of the Association, the President will call an emergency meeting of the Executive and Council. In the event that the issue of concern is Associated with the President or the President is not able to act, a Vice-President of IATUR will call the emergency meeting.
Circumstances under which the Executive and Council may consider disciplinary action against a member (Active, Current or former, individual or institutional) include the following:
Engaging in bullying, threatening, intimidating, violent or criminal behaviour against any IATUR vzw member or participant in an IATUR event
Misusing IATUR vzw funds or resources
Taking any action or failure to take action which leads to the exposure of a participant in a time use survey or causes any harm to a time use survey participant
Taking any action or failure to take action which leads to damage to public confidence in time use surveys
Any other action or failure to act which brings the methodology or field into disrepute or poses challenges to the legitimacy or standing of the Association
After the Executive and Council reach a majority decision, the President (or Vice-President, in cases where the incident involves the President or where the President is not able to act) will release a public statement.
Association rules only apply to members (Active or Current, individual or institutional), but IATUR vzw may need to make a public statement to disassociate itself from the bad practice of other parties
In the event the President (or a Vice-President) calls an emergency meeting in relation to one or more IATUR vzw members, any member affected will be advised that a meeting has been called
The President (or Vice-President in cases where the incident involves the President or the President is not able to act) holds discretion to determine if the affected member(s) should participate during part of the meeting or have an opportunity to reply following the meeting
Normally responses to situations of concern to the Association will be addressed in the public statement from the President (or Vice-President as necessary). In extreme circumstances, the Executive and Council may vote to suspend or expel the member, and to ban a former member from participating at future IATUR events. In the case of an Active Member, the expulsion only can be final after a decision of the General Assembly
The Association will provide affected members with a statement explaining any disciplinary decision. Affected members will have 6 weeks to file an appeal with the President. This period may be extended at the discretion of the Executive. A subsequent meeting of the Executive and Council will consider the appeal. If affected members do not accept the outcome, they may pursue mediation via any formal mediation service available in Belgium or consider legal action against the Association. Any decision taken by a majority vote of the Executive and Council following mediation is final
6. Disputes and mediation
(a) The grievance procedure set applies to disputes between
a Current Member and another Current Member; or
a Current Member and The Association
(b) The parties to the dispute must meet if practicable, or communicate by email or other methods to discuss the matter in dispute, and, if possible, resolve the dispute within 21 days after the dispute comes to the attention of all of the parties.
(c) If the parties are unable to resolve the dispute at the meeting or during their communication by email or other methods, or if a party fails to attend that meeting or reply to email or other communication methods, then the parties must, within 21 days, hold a meeting or communicate by email or other methods in the presence of a mediator.
(d) The mediator must be
a person chosen by agreement between the parties; or
in the absence of agreement, a person appointed by the Executive Committee of The Association
(e) A member of The Association or an independent party can be a mediator
(f) The mediator cannot be a party to the dispute
(g) The parties to the dispute must, in good faith, attempt to settle the dispute by mediation
(h) The mediator, in conducting the mediation, must
give the parties to the mediation process every opportunity to be heard; and
allow due consideration by all parties of any written statement submitted by any party; and
ensure that natural justice is accorded to the parties to the dispute throughout the mediation process
(i) The mediator must not determine the dispute
(j) If the mediation process does not result in the dispute being resolved, the IATUR Executive will issue a final statement of the Association position on the matter. After this statement is issued, aggrieved parties would need to resolve the dispute in accordance with the vzw legislation or otherwise at law if they do not accept the final statement.
7. Electronic International Journal of Time Use Research (eIJTUR)
The eIJTUR shall maintain a publicly accessible web-site and receive submissions from any person who has conducted original research in the field of time use research for consideration through the review process set out on the journal web site
The Council will review accounts and decide the working budget for running the journal during the annual Executive and Council meeting
IATUR will pay to have DOI numbers for eIJTUR articles
The Editors of eIJTUR shall exercise their discretion over the content of the Journal
8. The IATUR vzw Web Site
The IATUR vzw web site shall publish time use information and resources in the official language of the Association, as set out in the Statutes (English at present), as the Executive Committee deems necessary and practical, some information also may be posted in other languages
The Executive Committee shall exercise their discretion in all matters pertaining to the content of the IATUR vzw website
9. Andrew Harvey Fellowships
(a) IATUR devotes some funds to assist with the travel costs of students, academics, national statistical office staff and others seeking to present research at an IATUR conference. In principal these funds are aimed at students and people working in developing countries, though can be extended to anyone with financial need. IATUR vzw calls these travel support awards Andrew Harvey Fellowships in recognition of Professor Harvey's long service, first as Secretary-Treasurer, then as President of IATUR (prior to incorporation in Belgium).
(b) Rules
Awards contribute toward the cost of travel, board and accommodation
Awards provide supplementary funding, and applicants should seek alternative sources of funding in addition to the Andrew Harvey Fellowships
People can receive awards to present work, not simply to attend
Awards are available for use by full participants, not accompanying persons
Awards will be given to one author of a paper or poster, not to multiple authors
To receive an Andrew Harvey Fellowship, participants must register and pay for registration for the conference as well as pay the student / developing country level of IATUR vzw dues by the early registration deadline of the conference. IATUR vzw dues will not be refunded and conference registration only can be refunded in accordance with the procedures set out for each conference if an award recipient does not attend
Fellowships are offered to people who have not received awards to attend an IATUR conference previously before people who previously have received funding
Fellowships favour funding people from many backgrounds and many countries over funding multiple people from the same institution
Depending on funds available, IATUR vzw will strive to fund a substantial portion of the travel costs of 1 or 2 people, and offer small awards to others
Funding decisions are at the discretion of the Secretary, Treasurer and local organisers
Powered by: Research Group TOR, Vrije Universiteit Brussel


The Vinyl Factory will release titles from forthcoming UNKLE album THE ROAD.
James Lavelle will take over London's Lazarides gallery for an immersive celebration of his music outfit UNKLE, which celebrates its 25th anniversary next year.
Daydreaming with UNKLE Presents… THE ROAD: SOHO will be the first opportunity to hear collaborations with Keaton Henson, Mark Lanegan and Eska from the forthcoming UNKLE album THE ROAD. The material will be presented with new video commissions and released on vinyl via The Vinyl Factory.
The show also features the premiere of a new virtual reality installation from Somerset House's recent Daydreaming With…Stanley Kubrick exhibition, as well as paintings and special edition prints from a variety of artists and a programme of talks and film screenings.
"UNKLE has always been a multi-sensory creative project, ranging from genre-defining music to cutting-edge visual art. It therefore feels incredibly fitting to celebrate UNKLE's past, present and future in Soho, where it all began, with an immersive show at the much-loved Lazarides gallery," said James Lavelle.
Daydreaming with UNKLE Presents…THE ROAD: SOHO runs 20th January to 23rd February 2017 at Lazarides.


text:
Papouasie-Nouvelle-Guinée (174) > Sécurité sociale (Normes d'ensemble) (12)
Nom: Superannuation (General Provision) Act 2000 (No. 66 of 2000).
Pays: Papouasie-Nouvelle-Guinée
Sujet(s): Prestations de vieillesse, d'invalidité et de survivants
ISN: PNG-2000-L-82404
Bibliographie: Act on-line Pacific Islands Legal Information Institute (PacLII), University of the South Pacific PDF of Act as amended to 2006 (consulté le 2009-11-30)
Résumé/Citation: Makes provision for the licensing, regulation and supervision of superannuation funds, trustees, investment managers and fund administrators, the imposition of mandatory contributions to superannuation funds and to amend various Acts.
Amends the following Acts
- the National Provident Fund Act 1980 is amended in accordance with Schedule 5; and
- the Public Officers Superannuation Fund Act 1990 is amended in accordance with Schedule 6; and
- the Defence Force Retirement Benefits Act 1974 is amended in accordance with Schedule 7; and
- the Companies Act 1997 is amended in accordance with Schedule 8.
On the day on which the National Provident Fund becomes an authorized superannuation fund under Section 8, the National Provident Fund Act (Chapter 377) is repealed.
Texte(s) abrogé(s):
1980-08-07 (PNG-1980-L-11776)National Provident Fund Act (No. 18 of 1980).
2002 (PNG-2002-R-82405)Superannuation Regulation 2002 (No. 3 of 2002).
Texte(s) connexe(s):
1974 (PNG-1974-L-88007)Defence Force Retirement Benefits Act 1974 (Cap. 76).


What Does Queen Elizabeth II Do in a Day?
The queen's day is practically planned down to the second. Every moment is accounted for and Queen Elizabeth II knows what to expect when she wakes up in the morning. Follow along with what Her Majesty does in a day ahead.
The queen's maid goes about a specific routine when it comes to mornings. The maid brings the queen her 'morning tray' and turns on BBC Radio 4 because the queen enjoys listening to John Humphrys political show on the program, Today.
While the queen drinks her tea and listens to the radio, her maid gets started on running a bath. But not just any old bath.
The queen's maid must check the water temperature with a wooden-cased thermometer, according to the Daily Mail, to be sure the water is to the queen's liking. And the tub must not have too much water in it. No more than seven inches of water is acceptable.
The queen has designated dressers, people who lay out her clothes and help Her Majesty get dressed for the day ahead. Angela Kelly, the personal assistant to the queen, is responsible for the queen's wardrobe and oversees the dressers.
Once the queen is dressed, her hairdresser gets to work on her tresses.
One hour after she's gotten out of bed, the queen eats breakfast in her private dining room. Known to be particular about food, the queen typically dines on the same or very similar foods.
For breakfast, she's been known to favor cereal or sometimes oatmeal. While Queen Elizabeth II fuels up for the day ahead, a bagpiper plays music.
The queen catches up on the news and gets started on paperwork after breakfast. Her office isn't just for looks with its Chippendale desk.
"It may appear cluttered and untidy to the average eye, but the Queen knows where everything is and hates it if anything is moved without her permission," a former staff member told the Daily Mail.
The queen prefers fountain pens to ballpoint pens and has a crystal inkwell on her desk.
Once she's caught up on current events she calls for her private secretary who then brings a wicker basket to the queen's office containing papers Queen Elizabeth II will have to read and sign. It's during this time the queen discusses the details of any expected guests' stay.
The queen opens mail from personal friends, who know to denote letters with their initials in the bottom left-hand corner, signaling to staff to leave the letter unopened.
Audiences with the queen are at noon and last ten minutes in the appropriately-named Audience Room.
Then it's time for lunch. Typically Queen Elizabeth II eats a light lunch alone or with one of her kids. Her chef sends up a menu for meals the following week in French.
Why in French when she's the Queen of England? Because French has been the official language at Court since the reign of Queen Victoria when the head chef made French food and wrote the menus in French. The queen then takes a solo walk in the gardens where her staff know not to disturb her.
Any engagements are scheduled to end by 4:30 p.m. at the latest so the queen can be back at 5 p.m. for afternoon tea.
A creature of habit, the queen's afternoon tea menu rarely, if ever, changes. The menu includes crustless bite-size sandwiches i.e. finger sandwiches, warm scones with cream and strawberry jam, and Dundee fruit cake (the queen's favorite).
After tea and a snack, the queen may return to her office for another hour before getting ready for dinner. But on Tuesday nights, she has a standing meeting with the Prince Minister at 6:30 p.m. in the Audience Room.
Dinner often involves a tray dinner for Queen Elizabeth II. Not the kind from the frozen foods section of the grocery store but a tray nonetheless.
She usually eats dinner in her personal quarters, watching TV or reading a book. Oftentimes she'll have a working dinner where she continues going through the iconic red "boxes" containing official government documents.
Her Majesty always reads a rundown of Parliament proceedings during or immediately after dinner. The queen is in bed by 11 p.m. and enjoys reading before lights out.


text:
"A Christmas Story" playing in Cambridge
Production will be the first two weekends in December with pre-sale tickets available
"A Christmas Story" playing in Cambridge Production will be the first two weekends in December with pre-sale tickets available Check out this story on coshoctontribune.com: http://ohne.ws/2fLpctI
Published 2:10 p.m. ET Nov. 21, 2016
CAMBRIDGE - "A Christmas Story" will be at 7 p.m. Dec. 2, 3, 9 and 10 and at 4 p.m. Dec. 4 and 11 at the Cambridge Performing Arts Center, 642 Wheeling Ave., Cambridge.
The show directed by Alex Mullen, Taylor Pierce and Tricia Wurzbach is based on the famed story by Jean Shepherd about a little boy's Christmas in the 1940s. It was also turned into a popular holiday movie.
Tickets are $10 for adults, $8 for seniors and students and free for those under 2-years-old. Pre-sale tickets are available at Lady Jane's Mercantile next to the theater.
Read or Share this story: http://ohne.ws/2fLpctI
Recommended sentence doubled by judge
Footlight Players take on ABBA musical will make you say 'Mamma Mia'
Sisters return to their roots with Rusty Plow Press
Construction on Ridgewood's field house to begin soon
Two injured in ATV crash
Laci's tale: 6-year-old meets her favorite movie character