Submitted by Roberto Posenato on ; last update on

I took a degree in Computer Science in 1991 and a Ph.D. degree in Computational Mathematics in 1996 at the DSI - University of Milan (Italy).

My Ph.D. thesis is about approximability of optimization problem of quadratic functions in the Neural Networks and in the Spin Glasses range.

Now, I work as researcher (assistant professor) at the Science Faculty - State University of Verona.

### Temporal aspects on workflows

Workflow technology has emerged as one of the leading technologies in modelling, redesigning, and executing business processes. The management of temporal aspects in the definition of a workflow process has been considered only recently in the literature.

Currently available workflow management systems and research prototypes offer a very limited support for the

definition, detection, and management of temporal constraints over business processes.

I am collaborating with Prof. Carlo Combi to study such temporal aspects in order to propose new modelling systems that admit efficient methods to manage all temporal properties of the workflow instances.

### Approximation algorithms

For most optimization problems, resolution algorithms need computational resources that grow in super polynomial way as the instance dimension of the problem grows.

The *difficult* in design efficient algorithms can be formalized in the framework of the computational complexity theory showing that these problems are NP-complete and that it is not possible to find exact solutions in polynomial time under the conjecture that “P is no equal to NP”.

Therefore, a lot of studies have been conducted to discover approximate algorithms that work in polynomial time and to submit new classifications of NP-hard problems in respect to their approximation hardness.

A general approach for finding approximate solutions is the Hopfield neural network (1982). In this computational model, for all networks, an *energy* function can be associated to a network that finds a minimum of the function during its evolution.

Many optimization problems can be solved in an approximate manner by a reduction of the cost function to the energy function of a particular network. It is worth noting that the problem of minimum energy of Ising spin glasses is formally similar to the present problem.

Research results are:

- design of an efficient neural algorithm for the approximate solution of MAX-2SAT problem [2, 3, 7].
- design of a uniform circuit family for the development of the previous algorithm [2, 3, 7] and an efficient implementation on Voce su wikipedia">FPGA circuit [5, 7].
- design of two algorithms that calculate the minimum energy state for particular structure of Ising spin glasses [9] and the proof of a important lower bound about the approximability of minimum energy problem for such glasses [Ph.D thesis, 4, 10].
- design of an approximate algorithm for the selection of high-contrast color sets, that represent a very interesting problem in the framework of image processing [13].
- design of a new distributed algorithm for Max Independent Set problem that outperforms many other distributed heuristics for the same problem in terms of solution quality [14].

as a complementary result, we have found an upper bound to the mean of max cut of graphs [8].

Another interesting computational model to find approximate solutions is the *simple* genetic model, in which the individuals are represented by binary words of fixed length. It has been shown that the behaviour of a simple genetic system can be described in terms of homogeneous Markov chains whose states encode populations that are multi-sets of binary words. For this model, general theoretical results are available in the thermodynamic limit (for infinite populations) when the systems become deterministic iterative systems. Unfortunately, simulation of the deterministic system is computationally difficult since the states of the system are represented by vectors in R^{2w}, where *w* is the length of the words that represent the individuals. In a previous work, it has been introduced a genetic model, the BCCG model, that preserves most of the properties of the classical genetic systems but, for infinite populations, it has the states in R^{w} instead of R^{2w}. We propose a simplification of the BCCG model: a stochastic system with states in R^{w} even when the population size is finite (finite populations) [17].

### Web-graph analysis

Web graphs have special properties whose study requires a sizeable amount of mathematics, but also a careful study of actual web graphs.

I am collaborating with the members of the Laboratory for Web Algorithmics (LAW) - Dipartimento di Scienze dell'Informazione (DSI) of the Università degli studi di Milano to study the preference vector properties in the PageRank calculation.

### Web application technologies

For some time now I have been interested in studing and trying new technologies about web applications.

In the first period (1999-2000), we developed a simple framework based on the MVC-2 model to build data-intensive web applications. All the official web site of University of Verona are based on this framework [information page].

After we have proposed an original method to manage the internationalization of a database schema when it is necessary to internationalize a data-intensive web application [15, 16].