projet_optim_m2/main.tex

% ------------------------------------------------------------------------
\documentclass{llncs}
\input{prelude}
\begin{document} 
\title{Star Discrepancies for generalized Halton points}
% \titlerunning{}  % abbreviated title (for running head)
%                                     also used for the TOC unless
%                                     \toctitle is used

\author{Thomas Espitau\inst{1} \and Olivier Marty\inst{1}} 
%
% \authorrunning{} % abbreviated author list (for running head)
%
%%%% list of authors for the TOC (use if author list has to be modified)
% \tocauthor{}
%
\institute{
  $\mbox{}^1$ ENS Cachan \qquad
}

\maketitle

\makeatletter

\makeatother


\begin{abstract}
\end{abstract}


\section{Introduction}

\section{General architecture of the toolset}
   Big pipeline + pool + blabla\medskip

   Un truc bien ca serait d'avoir un truc modulaire (genre les heuristiques 
   sont des "blocs" et l'outil appelle un bloc quand il veut faire son test
   en l'appelant en multicore" 

   (c'est stupide mais ca fera un beau schéma!)



\section{Heuristics devlopped}

\subsection{Fully random search (Test case)}
  Blabla+pipeline
  \subsection{The Knuth-Fisher-Yates shuffle}

The Fisher–Yates shuffle is an algorithm for generating a random permutation 
of a finite sets. The Fisher–Yates shuffle is unbiased, so that every 
permutation is equally likely. We present here the Durstenfeld variant of 
the algorithm, presented by Knuth in \emph{The Art of Computrer programming}.
The algorithm's time complexity is here $O(n)$, compared to $O(n^2)$ of 
the naive implementation.

\begin{algorithm}[H]
  \SetAlgoLined
  \SetKwFunction{Rand}{Rand}
  \SetKwFunction{Swap}{Swap}
  \KwData{A table T[1..n]}
  \KwResult{Same table T, shuffled}
  \For{$i\leftarrow 1$ \KwTo $n-1$}{
     $j \leftarrow$ \Rand{$[1,n-i]$}\;
     \Swap{$T[i], T[i+j]$}\;
    }
  \caption{KFY algorithm}
\end{algorithm}


\begin{lemma}
  The resulting permutation of KFY is unbiaised.
\end{lemma}
\begin{proof}
  Let consider the set $[1,\ldots n]$ as the vertices of a random graph 
  constructed as the trace of the execution of the algorithm: 
  an edge $(i,j)$ exists in the graph if and only if the swap of $T[i]$ and
  $T[j]$ had been executed. This graph encodes the permutation represented by
  $T$. To be able to encode any permutation the considered graph must be connex 
  --- in order to allow any pairs of points to be swapped ---.
  Since by construction every points is reached by an edge, and that there 
  exists exactly $n-1$ edges, we can conclude directly that any permutation can
  be reached by the algorithm. Since the probability of getting a fixed graph 
  of $n-1$ edges with every edges of degree at least one is $n!^{-1}$, the 
  algorithm is thus unbiaised.

\end{proof}
\subsection{Local Search}
  Blabla+Pipeline
\subsection{Evolutionary heuristics}
  Blabla+Pipeline
\subsection{Genetic heuristics}
  Blabla+Pipeline

\section{Results}


\section{Conclusion}

\end{document}