Reliable Computations and their Applications
(with an emphasis on combining interval and 
constraint satisfaction techniques)

a Technical Track at 
the 20th ACM Symposium on Applied Computing 
March 13 - 17, 2005, Santa Fe, New Mexico, USA

Martine Ceberio 
University of Texas at El Paso
El Paso, TX, USA

Vladik Kreinovich
University of Texas at El Paso
El Paso, TX, USA

Michel Rueher  
Universite de Nice ESSI 
Sophia Antipolis, France

For the past nineteen years, the ACM Symposium on Applied 
Computing has been a primary gathering forum for applied 
computer scientists, computer engineers, software engineers, 
and application developers from around the world. 
SAC 2005 is sponsored by the ACM Special Interest 
Group on Applied Computing, and is hosted by New Mexico 
Institute of Mining and Technology, Socorro, NM, USA.

Many numerical computations, be it solutions to systems of
differential equations or optimization problems coming from applied
areas like protein folding, do not provide us with guaranteed
computation results. In many situations, we have numerical solutions,
we may even have a theorem guaranteeing that eventually, this numerical
solution tends to the actual precise one, but the algorithm itself
does not provide us with guaranteed bounds on the difference between the
numerical approximate solution and the desired actual one. 

Therefore, in some practical situations, numerical solutions 
are much farther from the actual (unknown) precise
solutions than the users assume. As a result, we often end up with
inefficient local maxima for practical optimization problems like
chemical engineering - or even with a mission failure if we are
planning, e.g., a spaceship trajectory. 

For some such algorithms, researchers have found guaranteed bounds, but
producing a guaranteed bound for each algorithm requires a lot of work. 

It is therefore desirable to develop a methodology that would provide
algorithms with automatic result verification, i.e., with
automatically generated upper bound on the difference between the
actual and the numerical solution. In other words, we need computation 
techniques that produce reliable (guaranteed) results. 

This problem was recognized already in the late 1950s when Lockheed 
wanted to develop algorithmic techniques guaranteeing
trajectories of spaceflights. These techniques, largely developed 
by Ramon E. Moore, were later applied to other 
practical problems where deviations from the target are of critical
importance. The main idea behind these techniques is that 
at any intermediate step of the computations, instead of the exact
number, we keep an interval of possible values. For inputs (that
usually come from measurements), we have an interval because
measurements are never 100% accurate; if the manufacturer of the
measuring instrument guarantees that the measurement error is D or
smaller, then the measuring result X means that the actual value is in
the interval [X-D,X+D]. At each elementary computational step, we
apply interval arithmetic to the corresponding intervals and produce
the interval for the result; e.g., [a,b]+[c,d] leads to [a+c,b+d]. 

Of course, this "straightforward interval computation", that does not
take dependence between intermediate results into consideration, does
not always lead to efficient estimates; however, in the last 40+
years, efficient interval computations methods have been developed
based on this original idea. There are a lot of interesting
applications of interval computations, there is a lot of potential,
but there are still numerous open problems, situations where new
techniques are needed. 

One such technique that has also been used to provide guaranteed
bounds is the technique of constraint propagation. This technique
originated in logical AI problems, and it has been lately successfully
applied to numerical problems, often in conjunction with interval
methods. For example, one of the latest textbooks on interval
computations, by Jaulin et al., contains robot-related practical
examples of combining these two techniques. This combination has
started, it is the object of interest by many researchers, it has
already led to interesting and efficient packages like Numerica, but
there is still a lot of room for potential improvement. 

We hope that our track, with an emphasis on such a combination, 
will bring together not only algorithm developers but also 
practitioners whose practical needs will help guide researchers 
in the proper directions. 

Authors are invited to submit original papers in all areas 
related to the track's topic. Possible submissions fall into 
the following categories:

* Original and unpublished research work
* Report of innovative computing applications in the arts, 
  sciences, engineering, and business areas 
* Report of successful technology transfer to new problem domains
* Report of industrial experience and demos of new innovative systems

Peer groups with expertise in the track focus area will blindly 
review submissions to that track. Accepted papers will be 
published in the annual conference proceedings. 

Papers should be submitted with no more that 4000 words. Accepted
papers must fit within five (5) two column pages, with the option (at
additional expense) to add three (3) more pages.

For submission, please use guidelines posted under Downloads at the 
SAC 2004 website. (There may be minor changes for submitting the 
final versions of accepted papers). 

Paper submissions should be sent to Track co-Chairs. 


Sept. 3, 2004:	Paper submissions
Oct. 15, 2004:	Author notification
Nov.  5, 2004:	Camera-Ready Copy

Nestled at 7000 feet (2 km) in the foothills of Rocky Mountains, 
Santa Fe, New Mexico, the "City Different", is the oldest capital city
in the United States, the city that has a long history and rich
cultural heritage. Originally a townlet populated by Pueblo Indians, 
it became a capital of Nueva Espana (New Spain) in 1607, then a 
capital of the Mexican state of Nuevo Mexico (New Mexico); 
since 1840s, it is part of the USA. 

Santa Fe is famous for its culture, art, and traditions. It is home to 
US's third largest art market, to the Santa Fe Opera, variety of
cuisines, hundreds of quaint shops, and unlimited outdoor
activities. For more information about Santa Fe see
the city website

[<--] Back to Forthcoming Conferences
[<--] Back to the main menu of the Interval Computations website