\documentclass[twoside,11pt]{article}

% Any additional packages needed should be included after jmlr2e.
% Note that jmlr2e.sty includes epsfig, amssymb, natbib and graphicx,
% and defines many common macros, such as 'proof' and 'example'.
%
% It also sets the bibliographystyle to plainnat; for more information on
% natbib citation styles, see the natbib documentation, a copy of which
% is archived at http://www.jmlr.org/format/natbib.pdf

\usepackage{cpl2e}

% Definitions of handy macros can go here

\newcommand{\dataset}{{\cal D}}
\newcommand{\fracpartial}[2]{\frac{\partial #1}{\partial  #2}}

% Heading arguments are {volume}{year}{pages}{submitted}{published}{author-full-names}

\cplheading{1}{2006}{1-48}{6/2006}{7/2006}{Jean-Charles R\'{e}gin}

% Short headings should be running head and authors last names

\ShortHeadings{}{Jean-Charles R\'{e}gin}
\firstpageno{1}

\begin{document}

\title{A Filtering Algorithm for Constraints of Difference in CSPs}

\author{\name Jean-Charles R\'{e}gin
        \email jcregin@ilog.sa \\
        \addr Ilog Sophia Antipolis \\
              Les Taissouni\`{e}res HB2 \\
              1681, route des Dolines \\
              06560 Valbonne, FranceIlog, SA
}

\editor{Pascal Van Hentenryck}

\maketitle

\begin{abstract}%   <- trailing '%' for backward compatibility of .sty
Many real-life Constraint Satisfaction Problems (CSPs) involve some
constraints similar to the alldifferent constraints. These constraints
are called constraints of difference. They are defined on a subset of
variables by a set of tuples for which the values occuring in the same
tuple are all different. In this paper, a new filtering algorithm for
these constraints is presented.  It achieves the generalized
arc-consistency condition for these non-binary constraints. It is
based on matching theory and its complexity is low. In fact, for a
constraint defined on a subset of $p$ variables having domains of
cardinality at most $d$, its space complexity is $O(pd)$ and its time
complexity is $O(p^{2}d^{2})$.  This filtering algorithm has been
successfully used in the system RESYN, to
solve the subgraph isomorphism problem.
\end{abstract}

\begin{keywords}
Alldifferent, Filtering Algorithms, GAC-Schema
\end{keywords}

\section{Introduction}

The constraint satisfaction problems (CSPs) form a simple formal frame
to represent and solve some problems in artificial intelligence. The
problem of the existence of solutions in a CSP is
NP-complete. Therefore, some methods have been developed to simplify
the CSP before or during the search for solutions. The consistency
techniques are the most frequently used.  Several algorithms achieving
arc-consistency have been proposed for binary CSPs
\cite{Mackworth77,Mohr86,Bessiere93,Bessiere94} and for n-ary CSPs
\cite{Mohr88b}. Only limited works have been carried out on the
semantics of contraints : \cite{Mohr88a} have described an improvement
of the algorithm AC-4 for special constraints introduced by a vision
problem, \cite{Vanhentenryck92a} have studied monotonic and functional
binary constraints. In this work, we are interested in a special case
of n-ary constraints : the constraints of difference, for which we
propose a filtering algorithm.

A constraint is called \emph{constraint of difference} if it is defined
on a subset of variables by a set of tuples for which the values
occuring in the same tuple are all different. They are present in many
real-life problems.

These constraints can be represented as n-ary constraints and filtered
by the generalized arc-consistency algorithm GAC4 \cite{Mohr88b}. This
filtering efficiently reduces the domains but its complexity can be
expensive.  In fact, it depends on the length and the number of all
admissible tuples. Let us consider a constraint of difference defined
on $p$ variables, which take their values in a set of cardinality
$d$. Thus, the number of admissible tuples corresponds to the number
of permutations of $p$ elements selected from $d$ elements without
repetition : $^{d}P_{p}= \frac{d!}{(d-p)!}$. Therefore some constraint
resolution systems, like CHIP \cite{vanhentenryck89}, represent these
n-ary constraints by sets of binary constraints. In this case, a
binary constraint of difference is built for each pair of variables
belonging to the same constraint of difference. But the pruning
performance of arc-consistency, for these constraints is poor. In
fact, for a binary alldifferent constraint between two variables $i$
and $j$, arc-consistency removes a value from domain of $i$ only when
the domain of $j$ is reduced to a single value.

% Acknowledgements should go at the end, before appendices and references

\acks{We would like to thank particularly Christian Bessi\`{e}re and also
  Marie-Catherine Vilarem, Tibor Kok\'{e}ny and the anonymous reviewers
  for their comments which helped improve this paper.}

% Manual newpage inserted to improve layout of sample file - not
% needed in general before appendices/bibliography.

\newpage

%\appendix
%\section*{Appendix A.}

\bibliography{sample}

\end{document}