From: Marie-Catherine VILAREM <mcvil>
Message-Id: <199505041450.QAA02896@sequoia.lirmm.fr>
To: dif, arc
Subject: call for papers
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Date: Thu, 04 May 95 16:50:39 +0200


------- Forwarded Message

Return-Path: jegou@gyptis.univ-mrs.fr
Received: from gyptis.univ-mrs.fr (protis.univ-mrs.fr [193.50.130.3]) by 
lirmm.lirmm.fr (8.6.10/8.6.4) with SMTP id RAA13396 for <mcvil@lirmm.fr>; Wed, 
3 May 1995 17:44:02 +0200
Received: by gyptis.univ-mrs.fr (4.1/1.34)
	id AA20691; Wed, 3 May 95 17:41:39 +0100 
Date: Wed, 3 May 95 17:41:39 +0100
From: jegou@gyptis.univ-mrs.fr (Philippe JEGOU)
Message-Id: <9505031641.AA20691@gyptis.univ-mrs.fr>
To: mcvil


**********************************************************************
                          Call for papers

     CP95 Workshop on Studing and Solving Really Hard Problems

                         23 september 1995
            At CP95, the First International Conference
       on Principles and Practice of Constraint Programming
                    Cassis / Marseille, France

 
Many interesting problems studied in the area of constraint programming are 
NP-hard. The canonical example is the Boolean satisfiability problem (SAT),
which provides an efficient encoding for all other NP-complete problems.
Despite the fact that these problems are inherently intractable (unless P=NP), 
a large number of methods have been proposed in recent years to solve such 
problems in practice, such as Stochastic Search, Simulated Annealing, Genetic 
Algorithms, Tabu search, Heuristics, Local Propagation etc. In order
to evaluate these methods, there has been much recent activity on
identifying the hardest problem instances of the various problem classes.
These hardest instances are often located in a phase transitions region
in the problem space. Further insights into the hardest problem instances also
come from the study of tractable sublasses of intractable problems, such as,
Horn theories, acyclic CSPs, etc.

This workshop tries to explore new advances in these domains. So, the
topics of interests include the folowing (non exhaustive list) :

    - complete versus incomplete algorithms,
    - probabalistics algorithms,
    - heuristics,
    - polynomial classes of instances,
    - transition phase on random problems.

We are interested in work on a spectrum of NP-Complete problems (SAT, 
CSPs, Linear Programming, Operation research, Combinatorics, and Graph Theory).

CP95 is an inter-disciplinary meeting focussing on constraint
programming and constraint-based systems. In runs from Tuesday 19 until
Friday 22 September 1995.

Attendance at the workshop will be by invitation of the organizers. If
space permits, everybody is welcome, but authors of accepted papers,
attendees at the main conference, and those expressing an interest now
(see below) will be given priority.

Authors are invited to submit papers not exceeding 18 pages, printed in
12pt, to the Workshop Organizers listed below. Shorter papers (around 4
pages) are also acceptable. We encourage authors to submit by electronic
mail, preferably in self-contained Postscript printable files. However a
printed reference copy should be sent anyway by express or courier mail.
Each submission, both by ordinary mail or by e-mail, should be accompanied
by a separate message to jegou@gyptis.univ-mrs.fr with a single postal
and e-mail address for communication, complete title, author(s), affiliation(s)
and 200 word abstract.

The accepted papers will be distributed at the workshop. People interested
in attending this workshop are encouraged to send an expression of interest
by electronic mail to jihad.jaam@lim.univ-mrs.fr as soon as possible.


Workshop Organizers and contact for submissions and all enquiries:

Jihad Jaam
LIM - URA CNRS 1787
Faculte des Sciences de Luminy
163, avenue de Luminy, Case 901
13288 Marseille Cedex 9
FRANCE

email : jihad.jaam@lim.univ-mrs.fr
tel : (33) 91 26 93 58 (voice)
tel : (33) 91 26 92 75 (fax)

Philippe Jegou                                  
LIM - URA CNRS 1787
Centre de Mathematiques et d'Informatique (CMI)
39, rue Joliot Curie
Technopole de Chateau-Gombert
13453 Marseille Cedex 13
FRANCE

email : jegou@gyptis.univ-mrs.fr (send your papers to this adress)
tel : (33) 91 11 36 05  or (33) 91 11 36 00 (voice)
tel : (33) 91 11 36 02 (fax)

Important Dates :

       Submission deadline : 10 June 1995
       Notification of acceptance : 28 July 1995
       Camera-ready version : 04 September 1995
       Worhshop date : 23 September 1995

Program Chairs:

       Bart Selman         (selman@research.att.com)
       Pierre Siegel       (siegel@gyptis.univ-mrs.fr)

Program Commitee:

       Peter Cheeseman     (cheeseman@pluto.arc.nasa.gov)
       Olivier Dubois      (dubois@laforia.ibp.fr)
       Eugene Freuder      (ecf@cs.unh.edu)
       Scott Kirkpatrick   (kirk@watson.ibm.com)
       Jihad Jaam          (jihad.jaam@lim.univ-mrs.fr)
       Philippe Jegou      (jegou@gyptis.univ-mrs.fr)
       Antoine Rauzy       (Antoine.Rauzy@labri.u-bordeaux.fr)
       Bart Selman         (selman@research.att.com)
       Pierre Siegel       (siegel@gyptis.univ-mrs.fr)
       Edward Tsang        (edward@sx.ac.uk)

------- End of Forwarded Message