Recent Papers by Roberto Battiti
LIONLab (machine Learning and Intelligent Optimization)
University of Trento, Italy

bb2016blm
Mauro Brunato and Roberto Battiti
A Telescopic Binary Learning Machine for Training Neural Networks
IEEE Transactions on Neural Networks and Learning Systems, Accepted for publication, 2016.
Manuscript Number: TNNLS-2015-P-5760
Print ISSN: 2162-237X
Online ISSN: 2162-2388
Digital Object Identifier: 10.1109/TNNLS.2016.2537300

PDF: battiti-blm-ieee-tnnls.pdf

bb2016ijcnn
Mauro Brunato and Roberto Battiti
X-MIFS: Exact Mutual information for Feature Selection
Proc. 2016 International Joint Conference on Neural Networks , July 24-29, Vancover, Canada, accepted for oral presentation and publication, 2016.

PDF: (preprint) battiti-wcci2016.pdf

bb2016informatica
Mauro Brunato and Roberto Battiti
CoRSO (Collaborative Reactive Search Optimization): Blending Combinatorial and Continuous Local Search
Informatica, An international journal, Accepted for publication, 2016.

PDF: (local preprint copy) battiti-informatica-preprint.pdf

The-LION-way-book
LIONbook
The LION way. Machine Learning plus Intelligent Optimization.
R. Battiti and M. Brunato
LIONlab, University of Trento, Italy, Version 2.0, Apr 2015.

BibTex:
@book{LIONway2015
   author = "Roberto Battiti and Mauro Brunato",
   title = "The LION way. Machine Learning {\em plus} Intelligent Optimization",
   publisher = "LIONlab, University of Trento, Italy",
   year = "2014",
   isbn = "978-14-960340-2-1"
}


Reactive-Search-And-Intelligent-Optimization-Book

Reactive Search and Intelligent Optimization, by R. Battiti, M. Brunato and F. Mascia

Abstract: This book is about learning for problem solving. [...] Human problem solving is strongly connected to learning. Learning takes places when the problem at hand is not well known at the beginning, and its structure becomes more and more clear when more experience with the problem is available. [...] What is critical for men is critical also in many human-developed problem solving strategies. It is not surprising that many methods for solving problems in Artificial Intelligence, Operations Research and related areas, follow the search scheme [...]
We aim at giving the main principles and at developing some fresh intuition for the approaches. We like mathematics but we also think that hiding the underlying motivations and sources of inspiration takes some color out of the scientific work [...]. On the other hand, pictures and hand-waving can be very dangerous in isolation and we try to avoid these pitfalls by giving also the basic equations when possible, or by at least directing the reader to the bibliographic references for deepening a topic. The point of view of the book is to look at the zoo of different optimization beasts to underline opportunities for learning and self-tuning strategies.
(From the Introduction)
BibTex:
@BOOK{BBM2008,
  AUTHOR =       {Roberto Battiti and Mauro Brunato and Franco Mascia},
  TITLE =        {Reactive Search and Intelligent Optimization},
  PUBLISHER =    {Springer Verlag},
  YEAR =         {2008},
  series =       {Operations research/Computer Science Interfaces},
  note =         {ISBN: 978-0-387-09623-0},
  ulr =          {http://www.springer.com/978-0-387-09623-0}
}
Preprint of book (PDF) Reactive-Search-and-Intelligent-Optimization-Battiti-Brunato-Mascia-preprint.pdf
cbp2015
Paolo Campigotto; Roberto Battiti; Andrea Passerini
Learning Modulo Theories for preference elicitation in hybrid domains
Preprint, under revision.

PDF: (local preprint copy) CLEO_paper.pdf
bb2015ijcnn
Mauro Brunato and Roberto Battiti
Stochastic Local Search for Direct Training of Threshold Networks
Proc. 2015 International Joint Conference on Neural Networks , pag. 1-8, 2015.
journal link ( DOI: 10.1109/IJCNN.2015.7280770 )
PDF: (local copy) battiti-ijcnn2015.pdf
Link to IJCNN Conference: IJCNN 2015 - Killarney


ZHANG2014
Liangjun Ke, Qingfu Zhang and Roberto Battiti
Hybridization of Decomposition and Local Search for Multiobjective Optimization
IEEE Transaction on Cybernetics , vol. 44, no. 10, October 2014, pag. 1808-1820.
DOI: 10.1109/TCYB.2013.2295886

PDF: (local cache copy) hybridization-2014.pdf
Link to IEEE publication: IEEE Xplore Digital Library
ICDM2013
Duy Tin Truong, Roberto Battiti and Mauro Brunato
Discovering Non-Redundant Overlapping Biclusters on Gene Expression Data,
Proceedings The IEEE 13th International Conference on Data Mining series (ICDM 2013) , Dallas, Texas / December 7-10, 2013, pages 747-756.
IEEE Computer Society
. DOI 10.1109/ICDM.2013.36
PDF proofs: biclustering-icdm2013.pdf
MICS2013-BP
Dinara Mukhlisullina, Andrea Passerini, Roberto Battiti
Learning to diversify in complex interactive Multiobjective Optimization
Best Paper Award MIC 2013: The X Metaheuristics International Conference , Singapore, Aug 5-8, 2013, Singapore.
MIC 2013 website
PDF (preprint) MIC-BEST-paper.pdf
MICS2013-ALPI
Paolo Campigotto, Andrea Passerini, and Roberto Battiti
Active learning of Pareto fronts with disconnected feasible decision and objective spaces
MIC 2013: The X Metaheuristics International Conference , Singapore, Aug 5-8, 2013, Singapore.
MIC 2013 website
PDF (preprint) MIC-ALPI.pdf
TNNLS2013
Paolo Campigotto, Andrea Passerini, and Roberto Battiti
Active learning of Pareto fronts
IEEE Transactions on Neural Networks and Learning Systems , Volume:25 , Issue: 3, March 2014 Page(s): 506 - 519
ISSN : 2162-237X INSPEC Accession Number: 14111769
Digital Object Identifier: 10.1109/TNNLS.2013.2275918
PDF (preprint) alp-2014.pdf

Abstract: This work introduces the Active Learning of Pareto fronts (ALP) algorithm, a novel approach to recover the Pareto front of a multi-objective optimization problem. ALP casts the identification of the Pareto front into a supervised machine learning task. This approach enables an analytical model of the Pareto front to be built. The computational effort in generating the supervised information is reduced by an active learning strategy. In particular, the model is learnt from a set of informative training objective vectors. The training objective vectors are approximated Pareto-optimal vectors obtained by solving different scalarized problem instances. The experimental results show that ALP achieves an accurate Pareto front approximation with a lower computational effort than state-of-the-art Estimation of Distribution Algorithms and widely-known genetic techniques.


TB2013
Duy Tin Truong and Roberto Battiti
A flexible cluster-oriented alternative clustering algorithm for choosing from the Pareto front of solutions
Machine Learning , Accepted: 3 April 2013.
Published online: 24 April 2013 at (springer.com) DOI 10.1007/s10994-013-5350-y
PDF (preprint) cognac_journal.pdf

Abstract: Supervised alternative clustering is the problem of finding a set of clusterings which are of high quality and different from a given negative clustering. The task is therefore a clear multi-objective optimization problem. Optimizing two conflicting objectives at the same time requires dealing with trade-offs. Most approaches in the literature optimize these objectives sequentially (one objective after another one) or indirectly (by some heuristic combination of the objectives). Solving a multi-objective optimization problem in these ways can result in solutions which are dominated, and not Pareto-optimal. We develop a direct algorithm, called COGNAC, which fully acknowledges the multiple objectives, optimizes them directly and simultaneously, and produces solutions approximating the Pareto front. COGNAC performs the recombination operator at the cluster level instead of at the object level, as in the traditional genetic algorithms. It can accept arbitrary clustering quality and dissimilarity objectives and provides solutions dominating those obtained by other state-of-the-art algorithms. Based on COGNAC, we propose another algorithm called SGAC for the sequential generation of alternative clusterings where each newly found alternative clustering is guaranteed to be different from all previous ones. The experimental results on widely used benchmarks demonstrate the advantages of our approach.
Index Terms: Alternative clustering, Multi-objective optimization, Cluster-oriented recombination Genetic algorithms


TBB2013
Duy Tin Truong, Roberto Battiti and Mauro Brunato
A Repeated Local Search Algorithm for BiClustering of Gene Expression Data
In: E. Hancock and M. Pelillo (Eds.): Proceedings of SIMBAD 2013, LNCS 7953, pp. 281-296, 2013. , Springer Verlag.
PDF (preprint) simbad-2013.pdf

Abstract: Given a gene expression data matrix where each cell is the expression level of a gene under a certain condition, biclustering is the problem of searching for a subset of genes that coregulate and coexpress only under a subset of conditions. The traditional clustering algorithms cannot be applied for biclustering as one cannot measure the similarity between genes (or rows) and conditions (or columns) by normal geometric similarities. Identifying a network of collaborating genes and a subset of experimental conditions which activate the specific network is a crucial part of the problem. In this paper, the BIClustering problem is solved through a REpeated Local Search algorithm, called BICRELS. The experiments on real datasets show that our algorithm is not only fast but it also significantly outperforms other state-of-the-art algorithms.
Index Terms: biclustering, co-clustering, local search, gene expression, microarray.


KZB2012
Liangjun Ke, Qingfu Zhang, and Roberto Battiti
MOEA/D-ACO: A Multiobjective Evolutionary Algorithm Using Decomposition and Ant Colony
IEEE Transaction on Cybernetics ,
VOL. 43, NO. 6, DECEMBER 2013, pag. 1845-1859.
Digital Object Identifier 10.1109/TSMCB.2012.2231860
10.1109/TSMCB.2012.2231860 IEEE Explore
PDF (local cache copy) ACOD-published.pdf

Abstract: Combining ant colony optimization (ACO) and multiobjective evolutionary algorithm based on decomposition (MOEA/D), this paper proposes a multiobjective evolutionary algorithm, MOEA/D-ACO. Following other MOEA/D-like algorithms, MOEA/D-ACO decomposes a multiobjective optimization problem into a number of single objective optimization problems. Each ant (i.e. agent) is responsible for solving one subproblem. All the ants are divided into a few groups and each ant has several neighboring ants. An ant group maintains a pheromone matrix and an individual ant has a heuristic information matrix. During the search, each ant also records the best solution found so far for its subproblem. To construct a new solution, an ant combines information from its group's pheromone matrix, its own heuristic information matrix and its current solution. An ant checks the new solutions constructed by itself and its neighbors, and updates its current solution if it has found a better one in terms of its own objective. Extensive experiments have been conducted in this paper to study and compare MOEA/D-ACO with other algorithms on two set of test problems. On the multiobjective 0-1 knapsack problem, MOEA/D-ACO outperforms MOEA/D-GA on all the nine test instances. We also demonstrate that the heuristic information matrices in MOEA/D-ACO are crucial to the good performance of MOEA/D-ACO for the knapsack problem. On the biobjective traveling salesman problem, MOEA/D-ACO performs much better than BicriterionAnt on all the 12 test instances. We also evaluate the effects of grouping, neighborhood and the location information of current solutions on the performance of MOEA/D-ACO. The work in this paper shows that reactive search optimization scheme, i.e., the "learning while optimizing" principle, is effective in improving multiobjective optimization algorithms.
Index TermsAnt colony optimization (ACO) , decomposition , multiobjective 0-1 knapsack problem (MOKP) , multiobjective optimization , multiobjective traveling salesman problem (MTSP) , reactive search optimization (RSO).


TB2012
Duy Tin Truong, Roberto Battiti
A Cluster-Oriented Genetic Algorithm for Alternative Clustering
Proceedings The IEEE International Conference on Data Mining series (ICDM 2012) , Bruxelles, Belgium, Dec 10-13, 2012.
PDF proofs: PID2565417.pdf

Abstract: Supervised alternative clusterings is the problem of finding a set of clusterings which are of high quality and different from a given negative clustering. The task is therefore a clear multi-objective optimization problem. Optimizing two conflicting objectives requires dealing with trade-offs. Most approaches in the literature optimize these objectives sequentially or indirectly, resulting in solutions which are dominated. We develop a multi-objective algorithm, called COGNAC, able to optimize the objectives directly and simultaneously and producing solutions approximating the Pareto front. COGNAC performs the recombination operator at the cluster level instead of the object level as in traditional genetic algorithms. It can accept arbitrary clustering quality and dissimilarity objectives and provide solutions dominating those of other state-of-the-art algorithms. COGNAC can also be used to generate a sequence of alternative clusterings, each of which is guaranteed to be different from all previous ones.
Keywords: alternative clustering; multi-objective optimization; cluster-oriented; genetic algorithm.


Reactive-Business-Intelligence-book
reactive business intelligence Book cover
Reactive Business Intelligence. From Data to Models to Insight.
R. Battiti and M. Brunato,
Reactive Search Srl, Italy, February 2011.
ISBN: 978-88-905795-0-9

Abstract: It is obvious, you can see it! Think about how many times you intuitively associate clarity and real understanding with vision. The word intelligence itself derives from the Latin verb intelligere (coming from intus legere, "reading into something," a close cousin of "insight"), again related to reading and seeing. Humans are innately visual creatures and a big portion of our brain is devoted to processing visual information. Our ancestors needed to be very fast to identify predators in the jungle and to react accordingly. They did not survive and transmit genes if they did not. We need to be very fast to transform huge amounts of information into insight, knowledge, engineering designs, choices, decisions.
We decided to unite in this book aspects related to modeling and aspects related to visualizing data and models. We are concerned with explanations of our world which can be used, used to predict, used to build tools. This means measuring objects and events, mining and analyzing massive amounts of data, and discovering interesting relationships emerging from the data. Visual analytics is a term used to denote analytical reasoning facilitated by interactive visual interfaces. The effort is surely related to data mining, the process of automatically extracting interesting patterns from massive amounts of data. We prefer the term Reactive Business Intelligence (RBI) to underline its practical orientation and the fast reaction implied by two basic learning components, one connecting the user to the software, a second one internal to the software, through automated and intelligent self-tuning methods. A connection between visualization and problem-solving strategies is also at the heart of RBI: the decision maker can be, and should be, in an interactive loop, rapidly reacting to first results and visualizations to direct the subsequent efforts to suit his needs and preferences.
(From the Introduction)
The material in this book is now extended and updated in our LION way but pls contact me if you are still interested in this particular book.


BB2011
Mauro Brunato and Roberto Battiti
R-evo: A Reactive Evolutionary Algorithm for the Maximum Clique Problem
IEEE Transactions on Evolutionary Computation , Volume: 15 Issue:6, page(s): 770-782, ISSN: 1089-778X, Digital Object Identifier: 10.1109/TEVC.2010.2043363, December 2011.
link to IEEE Transactions on Evolutionary Computation paper
PDF proofs: revo-2011.pdf

Abstract: see also AbstractPlus
An evolutionary algorithm with guided mutation (EA/G) has been proposed recently for solving the maximum clique problem. In the framework of estimation-of-distribution algorithms, guided mutation uses a model distribution to generate offspring by combining the local information of solutions found so far with global statistical information. Each individual is then subjected to a Marchiori's repair heuristic, based on randomized extraction and greedy expansion, to ensure that it represents a legal clique. A novel reactive and evolutionary algorithm R-EVO proposed in this paper starts from the same evolutionary framework but considers more complex individuals, which modify tentative solutions by local search with memory, according to the reactive search optimization (RSO) principles. In particular, the estimated distribution is used to periodically initialize the state of each individual based on the previous statistical knowledge extracted from the population. We demonstrate that the combination of the estimation-of-distribution concept with RSO produces significantly better results than EA/G for many test instances and it is remarkably robust with respect to the setting of the algorithm parameters. R-EVO adopts a drastically simplified low-knowledge version of reactive local search (RLS), with a simple internal diversification mechanism based on tabu-search, with a prohibition parameter proportional to the estimated best clique size. R-EVO is competitive with the more complex full-knowledge RLS-EVO that adopts the original RLS algorithm. For most of the benchmark instances, the hybrid scheme version produces significantly better results than EA/G for comparable or a smaller central processing unit time.


BBlum2010
C. Blum and R. Battiti (Eds.)
Proceedings of Learning and Intelligent OptimizatioN LION 4, Jan 18-22, 2010, Venice, Italy. Lecture Notes in Computer Science Volume 6073, 2010, DOI: 10.1007/978-3-642-13800-3, pag. 232-246
Digital version available: SpringerLink site


CPB2010
Paolo Campigotto, Andrea Passerini and Roberto Battiti
Handling concept drift in preference learning for interactive decision making.
Proceedings of HaCDAIS 2010: International Workshop on Handling Concept Drift in Adaptive Information Systems, Barcelona, Spain, Sep 2010. Mykola Pechenizkiy and Indre Zliobaite (Eds.), pag. 29-40. (online publications)
Digital version available: hacdais2010.pdf , workshop page .


BACA2011
Roberto Battiti and Paolo Campigotto
An Investigation of Reinforcement Learning for Reactive Search Optimization.
Youssef Hamadi and Eric Monfroy (Eds.)Autonomous Search, Springer Verlag, 2011.
Digital version available: autonomous-chapter10.pdf


CAPABA2011
Paolo Campigotto, Andrea Passerini, and Roberto Battiti
Active Learning of Combinatorial Features for Interactive Optimization.
Proceedings of LION5, Learning and Intelligent OptimizatioN, Rome - Italy, Jan 17-21, Springer Verlag, (Editor Carlos A.Coello Coello), volume 6683, series: Lecture Notes in Computer Science, 2011, pages 336-350.
link to Springer book , link to Springer book paper ,
Digital version available: LION5-campigotto-pub.pdf


PRIB2010
Stefano Teso1, Cristina Di Risio, Andrea Passerini, and Roberto Battiti
An On/Off Lattice Approach to Protein Structure Prediction from Contact Maps.
. Proceedings Pattern Recognition in Bioinformatics (PRIB2010), Lecture Notes in Bioinformatics (LNBI), 2010
Digital version available: prib2010.pdf


BB2010b
Roberto Battiti and Paolo Campigotto
Reactive Search Optimization: Learning While Optimizing. An Experiment in Interactive Multi-Objective Optimization.
Proceedings of MIC2009, VIII Metaheuristic International Conference, 2010.
Digital version available: mic2009.pdf


BBc2010
R. Battiti and M. Brunato
Reactive Search Optimization: Learning while Optimizing
Michel Gendreau and Jean-Yves Potvin (Eds.), Handbook of Metaheuristics (2nd edition), Series: International Series in Operations Research & Management Science, Vol. 146, 2010. Springer Science+Business Media, LLC 2010, pag. 543--571.
DOI 10.1007/978-1-4419-1665-5_18
Digital version available: handbook2009.pdf , Springer link


BP2010
Roberto Battiti and Andrea Passerini
Brain-Computer Evolutionary Multi-Objective Optimization (BC-EMO): a genetic algorithm adapting to the decision maker
IEEE Transactions on Evolutionary Computation, Vol. 14, Issue 15, pag. 671 - 687, 2010. Digital Object Identifier : 10.1109/TEVC.2010.2058118
PDF proofs: bcemo.pdf
BC-EMO.tgz Software for Brain-Computer Evolutionary Multi-Objective Optimization (BC-EMO): a genetic algorithm adapting to the decision maker.


BB2010-IEEETEVO
R. Battiti and M. Brunato.
R-EVO: a Reactive Evolutionary Algorithm for the Maximum Clique Problem
IEEE Transactions on Evolutionary Computation, 2010.
PDF proofs: ieee-tevo.pdf
Abstract: An evolutionary algorithm with guided mutation (EA/G) has been proposed recently for solving the maximum clique problem. In the framework of estimation-of-distribution algorithms (EDA), guided mutation uses a model distribution to generate offspring by combining the local information of solutions found so far with global statistical information. Each individual is then subjected to a Marchiori's repair heuristic, based on randomized extraction and greedy expansion, to ensure that it represents a legal clique. A novel reactive and evolutionary algorithm (R-EVO) proposed in this paper starts from the same evolutionary framework but considers more complex individuals, which modify tentative solutions by local search with memory, according to the Reactive Search Optimization (RSO) principles. In particular, the estimated distribution is used to periodically initialize the state of each individual based on the previous statistical knowledge extracted from the population. We demonstrate that the combination of the estimation-of-distribution concept with RSO produces significantly better results than EA/G for many test instances and it is remarkably robust w.r.t. the setting of the algorithm parameters. R-EVO adopts a drastically simplified low-knowledge version of Reactive Local Search (RLS), with a simple internal diversification mechanism based on tabu-search, with a prohibition parameter proportional to the estimated best clique size. REVO is competitive with the more complex full-knowledge RLSEVO which adopts the original RLS algorithm. For most of the benchmark instances, the hybrid scheme version produces significantly better results than EA/G for comparable or a smaller CPU time.
Index Terms: Maximum Clique, Reactive Search Optimization (RSO), Estimation of Distribution, guided mutation


BB2010
Mauro Brunato and Roberto Battiti
Grapheur: A Software Architecture for Reactive and Interactive Optimization
Proceedings Learning and Intelligent OptimizatioN LION 4, Jan 18-22, 2010, Venice, Italy. Lecture Notes in Computer Science Volume 6073, 2010, DOI: 10.1007/978-3-642-13800-3, pag. 232-246
Digital version available: grapheur-lion4.pdf


HAIFA2009
Roberto Battiti
Graph and hyper-graph partitioning
Invited presentation at the 9th Haifa Workshop on Interdisciplinary Applications of Graph Theory, Combinatorics and Algorithms, 20-21 May 2009, Haifa (Israel)
Slides: haifa.pdf.
ECCO2009
Roberto Battiti and Paolo Campigotto
Brain-machine optimization: learning objective functions by interacting with the final user
European Chapter on Combinatorial Optimization (ECCO) XXII , May 17-19, 2009, Jerusalem (Israel)
Slides: ecco09.pdf.
BM2009
Roberto Battiti and Franco Mascia
Reactive and Dynamic Local Search for Max-Clique: Engineering Effective Building Blocks.
Computers and Operations Research 37, issue 3 (March 2010) 534 -- 542
Digital version available (preprint): COR.pdf , permanent link to published version(DOI doi:10.1016/j.cor.2009.02.013 ) .
Abstract: This paper presents results of an ongoing investigation about how different algorithmic building blocks contribute to solving the Max- imum Clique problem. We consider greedy constructions, plateau searches, and more complex schemes based on dynamic penalties and/or prohibitions, in particular the recently proposed technique of Dynamic Local Search and the previously proposed Reactive Local Search (RLS). We design a variation of the original RLS algorithm where the role of long-term memory is increased (RLS-LTM). In addition, we consider in detail the effect of the low-level implementation choices on the CPU time per iteration. We present experimental results on randomly gen- erated graphs with different statistical properties, showing the crucial effects of the implementation, the robustness of different techniques, and their empirical scalability.


BC2008b
Roberto Battiti and Paolo Campigotto
Reinforcement Learning and Reactive Search: an adaptive MAX-SAT solver,
in ECAI 08: 18th European Conference on Artificial Intelligence, Patras, Greece, Jul 21-25, 2008.
Digital version available: reinforcement_ECAI08.pdf
Abstract: This paper investigates Reinforcement Learning (RL) applied to online parameter tuning in Stochastic Local Search (SLS) methods. In particular, a novel application of RL is proposed in the Reactive Tabu Search (RTS) scheme, where the appropriate amount of diversification in prohibition-based local search is adapted in a fast online manner to the characteristics of a task and of the local configuration. The experimental tests demonstrate promising results onMaximumSatisfiability (MAX-SAT) instances when compared with state-of-the-art SLS SAT solvers, such us AdaptNovelty+, rSAPS and gNovelty+.


BC2008
Roberto Battiti and Paolo Campigotto
Penalties may have collateral effects. A MAX-SAT analysis.
, in Workshop on Modeling and Solving Problems with Constraints (in conjunction with the 18th European Conference on Artificial Intelligence, ECAI 2008), Patras, Greece, Jul 21-22, 2008.
Digital version available: sideEffects_ECAI08.pdf
Abstract: Many incomplete approaches for MAX-SAT have been proposed in the last years. The objective of this investigation is not so much horse-racing (beating the competition on selected benchmarks) but understanding the qualitative differences between the various methods. In particular, we focus on reactive search schemes where taskdependent and local properties in the configuration space are used for the dynamic on-line tuning of local search parameters and we consider the choice between prohibition-based and penalty-based approaches. To abstract from implementation details we focus on the search trajectory characteristics and study the trade-off between diversification and bias after starting from a local minimizer. We then study the warping effects on the fitness surface of weight-update schemes and the resulting dynamics, through an exhaustive analysis of small MAX-SAT instances, and of the average evolution of individual trajectories. The results are compatible with the conclusion that penalty-based schemes achieve diversification from a starting local optimum through a complex method with global and potentially dangerous collateral effects, while prohibition-based schemes reach comparable or better results in a more direct and controllable manner. In the final part of this paper, we consider long runs of the complete algorithms on selectedMAX-SAT instances, which confirm the competitiveness of prohibition-based reactive approaches.


.
BM2007
Roberto Battiti and Franco Mascia
An Algorithm Portfolio for the Sub-Graph Isomorphism Problem
Proceedings of Stochastic Local Search 2007, Lecture Notes in Computer Science. Volume 4638/2007, Springer 2007, Pages 106-120.
Digital version available: Springer page , preprint: battiti_mascia_portfolio.pdf
Abstract: This work presents an algorithm for the sub-graph isomorphism problem based on a new pruning technique for directed graphs. During the tree search, the method checks if a new association between two vertices is compatible by considering the structure of their local neighborhoods, represented as the number of limited-length paths of different type originating from each vertex. In addition, randomized versions of the algorithms are studied experimentally by deriving their runtime distributions. Finally, algorithm portfolios consisting of multiple instances of the same randomized algorithm are proposed and analyzed. The experimental results on benchmark graphs demonstrate that the new pruning method is competitive w.r.t. recently proposed techniques. Significantly better results are obtained on sparse graphs. Furthermore, even better results are obtained by the portfolios, when both the average and standard deviation of solution times are considered.


MBW2008
Vittorio Maniezzo, Roberto Battiti and Jean-Paul Watson (Eds.)
Learning and Intelligent Optimization Second International Conference, LION 2007 II, Trento, Italy, December 8-12, 2007. Selected Papers Series: Lecture Notes in Computer Science
Subseries: Theoretical Computer Science and General Issues , Vol. 5313
Maniezzo, Vittorio; Battiti, Roberto; Watson, Jean-Paul (Eds.)
2008, XII, 243 p., Softcover
ISBN: 978-3-540-92694-8

Springer book page


BBC2008
Roberto Battiti, Mauro Brunato, Paolo Campigotto.
Learning while Optimizing an Unknown Fitness Surface.
Proc. 2nd Learning and Intelligent Optimization Workshop (LION2007 II, Trento, Italy, December 2007), pag. 25-40. LNCS 5313 - Springer, December 2008.
Digital version available: lionII-LSPI.pdf
Springer book page (DOI: 10.1007/978-3-540-92695-5_3)


BHB2008
Mauro Brunato, Holger H. Hoos, Roberto Battiti.
On Effectively Finding Maximal Quasi-Cliques in Graphs.
Proc. 2nd Learning and Intelligent Optimization Workshop (LION2007 II, Trento, Italy, December 2007). LNCS 5313 - Springer, December 2008.
Digital version available: lionII-quasi.pdf
Springer book page


BB2008
Mauro Brunato, Roberto Battiti
RASH: A Self-adaptive Random Search Method.
In: Carlos Cotta, Marc Sevaux, and Kenneth Sörensen (Eds.), Adaptive and Multilevel Metaheuristics. Studies in Computational Intelligence, Vol. 136, Springer, 2008. ISBN: 978-3-540-79437-0
Digital version available: RASH.pdf
Springer book page


CCGCB2008
ROBERTO G. CASCELLA, ZHEN CAO, MARIO GERLA, BRUNO CRISPO, ROBERTO BATTITI
Weak Data Secrecy via Obfuscation in Network Coding Based Content Distribution.
Accepted to the IFIP Wireless Days Conference, Dubai, United Arab Emirates, November 24-28 2008
Digital version available: ifip-2008.pdf


GCCCB2008
MARIO GERLA, ROBERTO G. CASCELLA, ZHEN CAO, BRUNO CRISPO, ROBERTO BATTITI
An efficient weak secrecy scheme for network coding data dissemination in VANET - Invited Paper.
In Proceedings of the IEEE International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC 2008), Cannes, France, September 15-18 2008, pages 1-5.
Digital version available: GCCCB08-VANET-PIMRC.pdf , IEEE Proceedings web site
Abstract: Vehicular networks create a new communication paradigm that enables to exploit the movement of cars to disseminate content. If network coding is used, vehicles have much more flexibility in content sharing and the system stability and scalability are promoted also in presence of mobility. Along this line, we propose an efficient mechanism to provide secrecy of the information. Traditional approaches based on encryption decrease the cooperation willingness of intermediate nodes, which have no expectation of recovering the file. Our scheme is based on obfuscation by processing and polluting the original file so that only the intended recipients, informed of corrupted blocks, can recover the information timely. We present several alternatives to efficiently provide weak secrecy and to foster cooperation. We simulate the file distribution in a vehicular network and show that the proposed scheme enhances content distribution in term of downloading speed and it is much more efficient than the ones that use encryption.


CB2007
ROBERTO G. CASCELLA, ROBERTO BATTITI
Social Networking and Game Theory to foster Cooperation.
Input paper at the 2nd ENISA Workshop on Authentication Interoperability Languages held at the ENISA/EEMA European eIdentity conference, Paris, France, June 12-13, 2007.
Digital version available: CB07-ENISA.pdf


BB2007
ROBERTO BATTITI, MAURO BRUNATO
R-EVO: a Reactive Evolutionary Algorithm for the Maximum Clique Problem
Technical report DIT-07-034 Università di Trento, May 2007
Digital version available: DIT-07-034.pdf


BB2007RS
Roberto Battiti and Mauro Brunato
REACTIVE SEARCH: MACHINE LEARNING FOR MEMORY-BASED HEURISTICS
Chapter 21 in: Teofilo F. Gonzalez (Ed.), Approximation Algorithms and Metaheuristics , Taylor & Francis Books (CRC Press), Washington, DC, 2007, pag. 21-1 -- 21-17
Digital version available: chap21.pdf
Abstract: Most state-of-the-art heuristics are characterized by a certain number of choices and free parameters, whose appropriate setting is a subject that raises issues of research methodology. In some cases, these parameters are tuned through a feedback loop that includes the user as a crucial learning component: depending on preliminary algorithm tests some parameter values are changed by the user, and different options are tested until acceptable results are obtained. Therefore, the quality of results is not automatically transferred to different instances and the feedback loop can require a lengthy \trial and error" process every time the algorithm has to be tuned for a new application. Parameter tuning is therefore a crucial issue both in the scientific development and in the practical use of heuristics. In some cases the role of the user as an intelligent (learning) part makes the reproducibility of heuristic results difficult and, as a consequence, the competitiveness of alternative techniques depends in a crucial way on the user's capabilities. Reactive Search advocates the use of simple sub-symbolic machine learning to automate the parameter tuning process and make it an integral (and fully documented) part of the algorithm. If learning is performed on line, task-dependent and local properties of the configuration space can be used by the algorithm to determine the appropriate balance between diversification (looking for better solutions in other zones of the configuration space) and intensification (exploring more intensively a small but promising part of the configuration space). In this way a single algorithm maintains the exibility to deal with related problems through an internal feedback loop that considers the previous history of the search. In the following, we shall call reaction the act of modifying some algorithm parameters in response to the search algorithm's behavior during its execution, rather than between runs. Therefore, a reactive heuristic is a technique with the ability of tuning some important parameters during execution by means of a machine learning mechanism. It is important to notice that such heuristics are intrinsically history-dependent; thus, the practical success of this approach in some cases raises the need of a sounder theoretical foundation of non-Markovian search techniques.


BG2007
Roberto Battiti and Anurag Garg
Digital Reputation for Virtual Communities
Chapter 85 in: Teofilo F. Gonzalez (Ed.), Approximation Algorithms and Metaheuristics , Taylor & Francis Books (CRC Press), Washington, DC, 2007, pag. 85-1 -- 85-16.
Digital version available: chap85.pdf
Abstract: A virtual community can be defined as a group of people sharing a common interest or goal who interact over a virtual medium, most commonly the Internet. Virtual communities are characterized by an absence of face-to-face interaction between participants which makes the task of measuring the trustworthiness of other participants harder than in nonvirtual communities. This is due to the anonymity that the Internet provides, coupled with the loss of audiovisual cues that help in the establishment of trust. As a result, digital reputation management systems are an invaluable tool for measuring trust in virtual communities. Trust is an important component of all human interactions whether they take place online or not. There is an implicit assumption of trust in each interaction that we participate in that involves some investment on our part. The Merriam-Webster dictionary defines trust as assured reliance on the character, ability, strength, or truth of someone or something. Even more pertinent to virtual communities is an alternative definition which states that trust is a dependence on something future or contingent; reliance on future payment for property (as merchandise) delivered. These definitions illustrate that the basis of trust is an expectation of future payment or reward and that the transaction partner will behave in an honest fashion and fulfill their obligations. The processes behind the creation of trust can be classified into four broad categories: 1. Personality-based trust. A person's innate disposition to trust others. 2. Cognitive trust. Through recognition of the characteristics of the transaction partner. 3. Institution-based trust. A buyer's perception that effective (third-party) institutional mechanisms are in place to facilitate transaction success. 4. Transaction-based trust. That relies on a participant's past behavior to assess their trustworthiness. Personality-based trust does not have a significant use in virtual communities where decisions on trust aremade algorithmically.Most cognitive factors that formtrust in real-life interactions such as the manner of a person, their body language, and the intonations of their speech are also absent in virtual communities. However, there are alternative formsof cognition that can be used instead. These are almost invariably based on the virtual identity of the communitymember. In most purely online contexts, as opposed to contexts where the online identity is linked to a nononline identity such as with online banking, there are virtually no costs to creating a new virtual identity.Obtaining an e-mail address on any of the free web-based e-mail services such asYahoo,Hotmail, Gmail is trivial andwith each one comes a new virtual identity.While these services are increasingly adopting strategies such as requiring image reading to counter automated registrationspamprograms, it is not difficult tocreate say adozen accounts in 10 min.Andas the e-Bay scam case showed, that is all a malicious user needs to surmount simple feedback systems and commit online fraud. Enforcing trust in virtual communities is hard not only because of the difficulties in recognizing the trustworthiness of participants but also because of the lack of adequate monitoring and appropriate sanctions for dishonest behavior. This lack of institution-based trust is because there are not enough trusted third parties with the power to punish to ensure honesty of all the players. This problem is exacerbated in decentralized virtual communities and electronic marketplaces. An organization like e-Bay with a centralized infrastructure can act as the trusted third party to at least store feedback information in a reliable fashion even though the information itself may not be reliable. The problem becomes much harder with decentralized systems such as peer-to-peer (P2P) networks where the absence of a centralized authority is a defining feature of the system. Hence, it appears that the best strategy for creating trust in virtual communities is through transactionbased trust where feedback on participants' past behavior is collected and aggregated to decide their trustworthiness. A transaction-based trust strategy is far from perfect and suffers from many of the same shortcomings as the other strategies. For instance, the lack of verifiable identities can make a transactionbased system vulnerable to manipulation. However, as many recent proposals have shown such strategies are not contingent upon a trusted third party and the community as a whole provides the institutional basis for trust. Hence, if the problem of identity can be solved, transaction-based systems are capable of providing the solution for virtual communities. Transaction-based trust creation strategies are also commonly known as reputation-based trust management systems or just reputation systems. Some authors use the term reputation systems narrowly to include only those systems that monitor past transactions of participants to compute their trustworthiness. This information is then shared with other participants who decide whether or not to interact with the target participant on its basis. We use the term in a more general sense to include recommendations systems that recommend items as well as systems that perform distributed authentication by inferring trustworthiness. All these systems have one feature in common: the collection and aggregation of feedback in order to rate objects or people. Reputation systems research lies at the intersection of several disciplines including evolutionary biology, economics (game theory and mechanism design), sociology (social network theory), and computer science (e-commerce, P2P systems, cryptography, etc.). In this chapter, we survey the approaches taken by researchers fromthese disciplines to provide the context for digital reputation schemes. We begin by listing the various applications of digital reputation systems. This is followed by a discussion of what motivates the participants of a virtual community to cooperate with each other.We then look at what are the requirements of a good reputation system. This is followed by a more detailed analysis of the components of reputation systems.We classify different types of feedback and their role in constructing reputations. We discuss second-order reputation and the motivations for providing feedback.Reputationmodifying factors such as transaction context are looked at next followed by a discussion on howreputations can be interpreted.We conclude by looking at several specific digital reputation systems that have been proposed.


LB2007
Bo Li and Roberto Battiti
Achieving optimal performance in IEEE 802.11 wireless LANs with the combination of link adaptation and adaptive backoff
Computer Networks 51 (2007), pag. 1574-1600.
Digital version available: cn2007.pdf (DOI doi:10.1016/j.comnet.2006.08.018)
Abstract: IEEE 802.11 is one of the most popular wireless LAN standards. In the paper, we propose a simple analytical model, which helps one obtain deep insight into the mechanism of achieving optimal performance by using IEEE 802.11 DCF (Distributed Coordination Function) protocol. The first contribution of this paper is the analysis of the optimal operation point where maximum goodput can be achieved. Through the analysis, we answer some fundamental questions about the existence and the uniqueness of the optimal operation point; about the maximum system goodput can be achieved; about the existence of a simple rule to check out if the system operates under the optimal state or not; and how do the data transmission rates, which is dependent on the selected physical transmission mode, and packet transmission errors, caused by channel fading and (or) interference, affect the final system performance. Another contribution is the proposal of a simple distributed adaptive scheme "LABS'' (i.e., Link adaptation and Adaptive Backoff Scheme), which makes the system operate under the optimal operation point and, at the same time, achieves some pre-defined target service differentiation ratio between different traffic flows. In the LABS, two adaptive schemes are combined: one is the so called "Link Adaptation'' scheme, which dynamically selects an optimal modulation mode at a given time so as to improve the achieved system goodput; the other one is the so called "Adaptive Backoff'' scheme, which adaptively adjusts the minimum contention window size of each sending node to guarantee that the system operates under (or near) the optimal operation point. Results obtained in the paper are relevant to both theoretical research and implementation of real systems.


SA2006
R. Battiti (Ed.)
ScienzAzienda 2006 Scienza e tecnologia per l'innovazione e lo sviluppo
Atti del convegno
8 maggio 2006 Facoltà di Scienze Matematiche Fisiche e Naturali, Università di Trento
Digital version available: sa.pdf


GMB2006
Garg, A. Montresor, A. Battiti, R.
Reputation Lending for Virtual Communities
Proceedings. 22nd International Conference on Data Engineering Workshops, 03-07 April 2006 (Digital Object Identifier: 10.1109/ICDEW.2006.128)
Digital version available: lending.pdf
Abstract: Reputation management schemes have recently emerged as a mechanism for improving trust and security in peer-topeer networks. A new entrant in a network with reputation management can either be given the benefit of doubt and be treated like a trusted (or semi-trusted) peer until it misbehaves or it can be assumed to be untrusted and have to earn the trust of others. The former case provides an incentive for misbehaving peers to cast off their old identity and assume a new one regularly. The latter case presents the problem of new peers being unable to bootstrap and to gain a foothold in the network. In this paper, we present a mechanism in which existing peers can choose to "lend" part of their reputation to new peers that they know in order to give them a start. This mechanism mirrors the real world where a reference or an introduction often gives one a foothold into an otherwise closed group. If the new peer behaves well, the old peer is rewarded for adding value to the group and if the new peer misbehaves the old peer loses the reputation it lent. In this way, existing peers have a stake in introducing new peers into the network and get a return on their investment for introducing honest peers.


AAA2003
Garg, A.; Battiti, R.; Cascella, R.G.;
"May I borrow Your Filter?" Exchanging Filters to Combat Spam in a Community
20th International Conference on Advanced Information Networking and Applications, AINA 2006, April 2006, Vienna.
IEEE Computer Society, Los Alamitos, CA, USA, Volume 2, 18-20 Page(s):489 - 493
Digital version available: aina2006.pdf
Abstract: Leveraging social networks in computer systems can be effective in dealing with a number of trust and security issues. Spam is one such issue where the "wisdom of crowds" can be harnessed by mining the collective knowledge of ordinary individuals. In this paper, we present a mechanism through which members of a virtual community can exchange information to combat spam. Previous attempts at collaborative spam filtering have concentrated on digest-based indexing techniques to share digests or fingerprints of emails that are known to be spam. We take a different approach and allow users to share their spam filters instead, thus dramatically reducing the amount of traffic generated in the network. The resultant diversity in the filters and cooperation in a community allows it to respond to spam in an autonomic fashion. As a test case for exchanging filters we use the popular SpamAssassin spam filtering software and show that exchanging spam filters provides an alternative method to improve spam filtering performance.


GB2005
Anurag Garg and Roberto Battiti
DIGITAL REPUTATION FOR VIRTUAL COMMUNITIES
Technical Report # DIT-05-066, Universita' di Trento, Oct 2005
Digital version available: TR-05-066.pdf
Abstract: In this report we provide an overview of digital reputation management systems for virtual communities. We begin with a discussion on the how trust is created in the real world. We then highlight how the process of trust creation differs in the virtual world. Next, we talk about the different ways in which digital reputations are useful to virtual communities such as incentivizing cooperation and punishing malicious users, providing recommendations or as a form of distributed authentication. We then discuss how evolutionary biology and game theory have informed research in reputation systems. This is followed by a discussion of the various components of reputation such as context, the forms of evidence, .rst and second order reputation and architectural considerations including the role of distributed hash tables in decentralized reputation management systems. We conclude with a discussion of some reputation management systems such as complaints-based trust, EigenTrust, PeerTrust and ROCQ.


BEBA2006
Sergei L. Bezrukov and Roberto Battiti
On Partitioning of Hypergraphs
Discrete Mathematics 307 (2007) 1737 - 1753
Digital version (preprint) available: hyperlast.pdf (DOI doi:10.1016/j.disc.2006.09.022 )
Abstract: We study Edge-Isoperimetric Problems (EIP) for hypergraphs and extend some technique in this area from graphs to hypergraphs. In particular, we establish some new results on a relationship between the EIP and some extremal poset problems, and apply them to obtain an exact solution of the EIP for certain hypergraph families. We also show how to solve the EIP on hypergraphs in some cases when the link to posets does not work. Another outcome of our results is a new series of hypergraphs admitting nested solutions in the EIP. The obtained results can be used for checking the quality of heuristics for hypergraph partitioning.


WB2006
Wei Wang and Roberto Battiti
Identifying Intrusions in Computer Networks with Principal Component Analysis
Proceedings of ARES 2006 (The First International Conference on Availability, Reliability and Security), 20-22 Apr 2006, Vienna, Austria, IEEE Computer Society, Los Alamitos, CA, USA. Pages 270-277.
Digital version available: ares2006.pdf
Abstract: Most current anomaly Intrusion Detection Systems (IDSs) detect computer network behavior as normal or abnormal but cannot identify the type of attacks. Moreover, most current intrusion detection methods cannot process large amounts of audit data for real-time operation. In this paper, we propose a novel method for intrusion identification in computer networks based on Principal Component Analysis (PCA). Each network connection is transformed into an input data vector. PCA is employed to reduce the dimensionality of the data vectors and identification is handled in a low dimensional space with high efficiency and low use of system resources. The normal behavior is pro- filed based on normal data for anomaly detection and models of each type of attack are built based on attack data for intrusion identification. The distance between a vector and its reconstruction onto those reduced subspaces representing the different types of attacks and normal activities is used for identification. The method is tested with network data from MIT Lincoln labs for the 1998 DARPA Intrusion Detection Evaluation Program and testing results show that the model is promising in terms of identification accuracy and computational efficiency for real-time intrusion identification.


BM2006
Roberto Battiti and Franco Mascia
Reactive and dynamic local search for Max-Clique, does the complexity pay off?
Technical Report DIT-06-027, Informatica e Telecomunicazioni, University of Trento, Apr 2006.
Digital version available: rls-dls.pdf
Abstract: This paper presents some preliminary results of an ongoing investigation about how different algorithmic building blocks contribute to solving theMaximumClique problem. In detail, we consider greedy constructions, plateau searches, and more complex schemes based on dynamic penalties and/or prohibitions, in particular the recently proposed technique of Dynamic Local Search and the previously proposed Reactive Local Search. The experimental results consider both the empirical hardness, measured by the iterations needed to reach empirical maxima, and the CPU time per iteration.


BBP2006
Mauro Brunato, Roberto Battiti and Srinivas Pasupuleti
A Memory-Based RASH Optimizer
Proceedings of the AAAI-06 workshop on Heuristic Search, Memory Based Heuristics and Their applications , July 17, Boston.
Digital version available: mrash-aaai.pdf
Abstract: This paper presents a memory-based algorithm for global optimization of multivariate functions of continuous variables. The proposed algorithm, M-RASH, is based on the RASH (Reactive Affine Shaker) heuristic, an adaptive search algorithm based only on point-wise function evaluations. MRASH is an extension of RASH in which promising starting points for local search trails are suggested online by using Bayesian Locally Weighted Regression. Both techniques maintain memory about the previous history of the search to guide the future exploration, but in very different ways. RASH compiles the previous experience into the shape of a local search area where sample points are drawn, while locally-weighted regression saves the entire previous history to be mined extensively when an additional sample point is generated. Because of the high computational cost related to the regression model, it is applied only to evaluate the potential of an initial point for a local search run. The experimental results show that M-RASH is indeed capable of leading to good results for a smaller number of function evaluations.


BG2005
Roberto Battiti and Mario Gerla
Proceedings of Tridentcom (First International Conference on Testbeds and Research Infrastructures for the Development of Networks and Communities), Feb 23-25 2005, Trento Italy
IEEE Computer Society, Los Alamitos, CA, USA, ISBN 0-7695-2219-X


PB2006
Srinivas Pasupuleti and Roberto Battiti
The Gregarious Particle Swarm Optimizer (G-PSO)
Proceedings of ACM Genetic and Evolutionary Computation Conference (GECCO) 2006 , July 8-12, 2006, Seattle, Washington, USA. ACM.
Digital version available: g-pso.pdf
Abstract: This paper presents a gregarious particle swarm optimiza- tion algorithm (G-PSO) in which the particles explore the search space by aggressively scouting the local minima with the help of only social knowledge. To avoid premature con- vergence of the swarm, the particles are re-initialized with a random velocity when stuck at a local minimum. Further- more, G-PSO adopts a "reactive" determination of the step size, based on feedback from the last iterations. This is in contrast to the basic particle swarm algorithm, in which the particles explore the search space by using both the individ- ual "cognitive" component and the "social" knowledge and no feedback is used for the self-tuning of algorithm parame- ters. The novel scheme presented, besides generally improv- ing the average optimal values found, reduces the computa- tion effort.


GBC2005
Anurag Garg, Roberto Battiti and Roberto Cascella
"Reputation management: experiments on the robustness of ROCQ"
In Proceedings of the 7th International Symposium on Autonomous Decentralized Systems (ISADS 2005) - First International Workshop on Autonomic Communication for Evolvable Next Generation Networks (WAGEN), Chengdu, China, 4-8 April 2005. IEEE Computer Society, 2005, pages 725-730.
Digital version available: isads2005.pdf


SGB2005
Mikalai Sabel, Anurag Garg, Roberto Battiti
WIKIREP: DIGITAL REPUTATION IN VIRTUAL COMMUNITIES
DIT Technical Report DIT-05-050, University of Trento, Italy, June 2005.
Digital version available: wikireptr-DIT-05-050.pdf Accepted for publication in Proceedings: CONGRESSO ANNUALE AICA 2005 , Comunita' virtuale dalla ricerca all'impresa, dalla formazione al cittadino, Udine, 5-7 ottobre 2005.
Abstract: We present a framework for applying digital reputations to collaborative environments, where multiple authors contribute to the same document. In our mechanism readers evaluate a single document, and reputation data derived from the feedbacks affect multiple authors and document versions. The digital reputation encourages contribution and provides motivation for active participation, leading to better quality of the content and to better user experience. Our approach is applicable to user-managed communities, distributed moderation systems, and other collaborative contexts. The underlying ideas of our scheme are: separate ratings for different versions of the same document, inheritance of previous ratings for newer versions, and appropriate allocation of credit to versions and authors. We describe in detail both the algorithms used to compute reputations, and our implementation, WikiRep, a reputation-enabled Wiki application.


BBP2005
Roberto Battiti, Mauro Brunato, Srinivas Pasupuleti
Do not be afraid of local minima: Affine Shaker and Particle Swarm
DIT Technical Report DIT-05-049, University of Trento, Italy, May 2005.

Digital version available: pso.pdf
Abstract: Stochastic local search techniques are powerful and flexible methods to optimize difficult functions. While each method is characterized by search trajectories produced through a randomized selection of the next step, a notable difference is caused by the interaction of different searchers, as exemplified by the Particle Swarm methods. In this paper we evaluate two extreme approaches, Particle Swarm Optimization, with interaction between the individual "cognitive" component and the "social" knowledge, and Repeated Affine Shaker, without any interaction between searchers but with an aggressive capability of scouting out local minima. The results, unexpected to the authors, show that Affine Shaker provides remarkably efficient and effective results when compared with PSO, while the advantage of Particle Swarm is visible only for functions with a very regular structure of the local minima leading to the global optimum and only for specific experimental conditions.


GPBG2005
Mario Gerla, Joon-Sang Park, Roberto Battiti, Anurag Garg
Intelligent Backbone Swarms for scalable, disruption tolerant wireless networking
Proceedings, 2005 IEEE Swarm Intelligence Symposium (SIS-05) June 8-10, 2005 Pasadena, California, USA, IEEE press, page 432 -- 435
Digital version available: swarm.pdf
Abstract: In this paper, we propose a swarm intelligence strategy for constructing a mobile backbone multicasting network which leads to improved scalability and connectivity compared to conventional flat networks. The strategy combines a simple clustering technique and On Demand Multicast Protocol (ODMRP). Also we show benefits of the mobile backbone network through a simulation study.


LBF2005
Bo LI, Roberto BATTITI, and Akira FUKUDA
Performance Analysis of a Service-dependant Handoff Scheme in Voice/Data Integrated Cellular Mobile Systems
Computer Networks, Volume 50, Issue 5, Pages 707-730 (April 2006)
Digital version available: COMNET-2005.pdf
Abstract: In this paper, we propose and analyze a service-dependent handoff and channel allocation scheme in voice and data integrated cellular mobile systems, which combines the ideas of "Variable Bandwidth" and "Preemptive Priority" together. In the scheme, voice and data traffic are considered. According to the variations of the offered traffic intensity at each cell, both a voice and a data call in service can occupy a full-rate channel or a half-rate channel. In order to guarantee the Quality of Service (QoS) for both voice and data traffic, channel resources are fairly shared between voice and data calls according to an optimal channel allocation scheme, which minimizes the difference between the average bandwidth of a voice call in service and that of a data call in service. To minimize the forced termination of a voice call, a voice call can preempt a data call in service if all the calls in the channel pool of the current cell are already assigned with half-rate service. The interrupted data call returns back to the queue specially prepared for data traffic. By analysis, we obtain the most important system performance measures. Comparisons with the scheme, which only supports "Preemptive Priority" without "Variable Bandwidth" supporting, shows that if the total arrival rate for originating calls is not very heavy, the new scheme can provide lower blocking probability and forced termination probability for both voice and data traffic, and shorter average total transmission time for a successfully completed data call.


BB2005
Mauro Brunato and Roberto Battiti
Statistical Learning Theory for Location Fingerprinting in Wireless LANs
Computer Networks, 47 (6), 2005, pages 825-845

Digital version available: ComNet.pdf
Abstract: In this paper, techniques and algorithms developed in the framework of Statistical Learning Theory are applied to the problem of determining the location of a wireless device by measuring the signal strength values from a set of access points (location fingerprinting). Statistical Learning Theory provides a rich theoretical basis for the development of models starting from a set of examples. Signal strength measurement is part of the normal operating mode of wireless equipment, in particular Wi-Fi, so that no special-purpose hardware is required. The proposed techniques, based on the Support Vector Machine paradigm, have been implemented and compared, on the same data set, with other approaches considered in scientic literature. Tests performed in a real-world environment show that results are comparable, with the advantage of a low algorithmic complexity in the normal operating phase. Moreover, the algorithm is particularly suitable for classification, where it outperforms the other techniques.


CBC2004
Anurag Garg, Roberto Battiti and Gianni Costanzi
Dynamic Self-management of Autonomic Systems: The Reputation, Quality and Credibility (RQC) Scheme
Proceedings of The 1st IFIP TC6 WG6.6 International Workshop on Autonomic Communication ( WAC2004, Berlin, 18-19 Oct 2004 ), Lecture Notes on Computer Science LNCS 3457, Michael Smirnov (Ed.), pag. 165-178, Springer, Berlin, 2005.
Digital version available: wac2004.pdf
Abstract: In this paper, we present a feedback-based system for managing trust and detecting malicious behavior in autonomically behaving networks. Like other distributed trust management systems, nodes rate the interactions they have with other nodes and this information is stored in a distributed fashion.
Two crucial insights motivate our work. We recognize as separate entities the trust placed in a node, {\em reputation}, and the trust placed in the recommendations made by a node, {\em credibility}. We also introduce the concept of quality of a trust rating.  Together, these two factors enhance the ability of each node to decide how much confidence it can place in a rating provided to it by a third party.
We implement our scheme on a structured P2P network, Pastry, though our results can be extended to generic autonomic communication systems. Experimental results considering different models for malicious behavior indicate the contexts in which the RQC scheme performs better than existing schemes.


LBC2004
Renato Lo cigno, Roberto Battiti, Marco Conti
Wireless on-demand network systems
Proceedings of the First Working Conference on Wireless On-demand Network Systems, WONS 2004 Madonna di Campiglio, Italy, January 21 - 23, 2004

Springer, LNCS vol. 2928, pages 402, 2004


LB2004
Bo Li and Roberto Battiti
Analysis of the IEEE 802.11 DCF with Service Differentiation Support in Non-saturation Conditions
Lecture Notes in Computer Science Volume 3266 / 2004 Quality of Service in the Emerging Networking Panorama: Fifth International Workshop on Quality of Future Internet Services, QofIS 2004, Barcelona, Spain.
Editors:  Josep Solé-Pareta, Michael Smirnov, Piet Van Mieghem, et al.
Publisher: Springer-Verlag Heidelberg
ISSN: 0302-9743, pp. 64 - 73.
Digital version (preprint) available: QoFIS2004final.pdf
Abstract: Although the performance analysis of the IEEE 802.11 Distributed Coordination Function (DCF) in saturation state has been extensively studied in the literature, little work is present on performance analysis in non-saturation state. In this paper, a simple model is proposed to analyze the performance of IEEE 802.11 DCF with service differentiation support in non-saturation states, which helps to obtain a deeper insight into the IEEE 802.11 DCF. Based on the proposed model, we can approximately evaluate the most important system performance measures, such as packet delays, which provide one with an important tool to predict and optimize the system performance. Moreover, a practical method to meet packet delay requirements is presented based on our theoretical results. Comparisons with simulations show that this method achieves the specified packet delay requirements with good accuracy.


SB2004
Elio Salvadori, Roberto Battiti

A Traffic Engineering Scheme for QoS Routing in G-MPLS Networks Based on Transmission Quality

In 8th IFIP Working Conference on Optical Network Design and Modelling - ONDM 2004 proceedings, 2004


SB2004
Salvadori E., Battiti R.,
"Quality of Service in IP over WDM considering both service differentiation and transmission quality". Proceedings "IEEE International Conference on Communications - ICC 2004", Paris - France, 20-24 June, 2004. IEEE, URL : http://www.icc2004.org/.

Digital preprint version available: qoswdm.pdf

CBCA2004
Csaba Kiss Kallo', Roberto Battiti, Carla-Fabiana Chiasserini, Marco Ajmone Marsan
Reducing the number of hops between communication peers in a bluetooth scatternet Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC2004) 21-25 March 2004, Atlanta, Georgia, USA. IEEE, Page(s):207 - 212. Vol.1

Digital preprint version available: wcnc2004.pdf

B2004
Roberto Battiti, Renato Lo Cigno, Mikalai Sabel, Fredrik Orava, Bjorn Pehrson
Wireless LANs: from WarChalking to Open Access Networks Monet (Mobile Networks and Applications), special issue dedicated to WMASH, guest editors: Giuseppe Bianchi, Sung Ju Lee, Parviz Kermani, no. 10, 275--287, 2005.

Digital version available: Battiti-Orava_05.ps , monet-2005.pdf

WILMA2003
R. Battiti, M. Brunato, R. Lo Cigno, A. Villani, R. Flor and G. Lazzari
WILMA: An Open Lab for 802.11 HotSpots
Lecture Notes in Computer Science
Publisher: Springer Berlin / Heidelberg
ISSN: 0302-9743
Subject: Computer Science
Volume 2775 / 2003
Title: PersonalWireless Communications
ISBN: 3-540-20123-8
DOI: 10.1007/b12004
Chapter: pp. 163 - 168

Digital version available: LNCS
Abstract:
WILMA (Wireless Internet and Location Management Architecture) is an ongoing research project based in Trento, Italy, whose aim is the study of the management of 802.11-based HotSpot Networks and the value added services that can be provided through such an infrastructure.
The WILMA project (www.wilmaproject.org) is supported by the Province of Trento under Grant N. 437, issued on March 3, 2002.


LB2003
Bo Li, Roberto Battiti
Performance Analysis of An Enhanced IEEE 802.11 Distributed Coordination Function Supporting Service Differentiation G. Kerlsson and M.I.Simirnov (Eds.): "Quality for all", QofIS 2003, LNCS 2811, pp. 152-161, 2003, Springer-Verlag Berlin.

Digital version available: QoFIS2003.pdf
Abstract: As one of the fastest growing wireless access technologies, Wireless LANs (WLANs) must evolve to support adequate degrees of service differentiation. Unfortunately, current WLAN standards like IEEE 802.11 Distributed Coordination Function (DCF) lack this ability. Work is in progress to define an enhanced version capable of supporting QoS for multimedia traffic at the MAC layer. In this paper, we aim at gaining insight into two mechanisms to differentiate among traffic categories, i.e., scaling the minimum contention window size and the length of the packet payload according to the priority of each traffic flow. We propose an analysis model to compute the throughput and packet transmission delays. In additions, we derive approximations to get simpler but more meaningful relationships among different parameters. Comparisons with simulation results show that a very good accuracy of performance evaluation can be achieved by using the proposed analysis model.


BBS2003
Mauro Brunato, Roberto Battiti, Elio Salvadori
Dynamic Load Balancing in WDM Networks
special issue di Optical Networks Magazine "Dynamic Optical Networking: Around the Corner or Light Years Away?", Sep 2003.
Digital version available: ONM.pdf
Abstract: In this paper new load balancing techniques are proposed based on IP-like routing, where the forwarding mechanism is only driven by the destination address. The aim of this work is to consider the applicability of this approach in the context of optical networks. The proposed algorithm (RSNE | Reverse Subtree Neighborhood Ex- ploration) implements a local search technique where the basic step is the modi cation of a single entry in the routing table of a node. A randomized method with reduced computational complexity (fRSNE | fast RSNE) is also presented and analyzed. Both schemes allow an incremental imple- mentation where local search steps are continuously performed as tra.c conditions change. Experiments under static and dynamic (time varying) tra.c scenar- ios show a rapid reduction of the congestion. The performance of the incremental scheme while tracking a changing tra.c matrix is compara- ble to that obtainable through the complete re-optimization of the tra.c, while the randomized implementation is particularly e.cient when scaling properties are considered.


Bat-per
R. Battiti.
Partially persistent dynamic sets for history-sensitive heuristics.
in: Data Structures, Near Neighbor Searches, and Methodology: Fifth and Sixth DIMACS Challenges, M. H. Goldwasser, D. S. Johnson And C.C. McGeoch, DIMACS Series in Discrete Mathematics and Theoretical Computer Science Volume 59, 2002, pag. 1 --21
Preprint available: persistent-challenge.ps

Abstract: Effective heuristic algorithms for combinatorial problems are based on integrating local neighborhood search with history-sensitive schemes, where the information collected during the previous search phase is used to direct the future effort. In particular, some algorithms (like REM tabu search and reactive tabu search) need to detect whether a configuration has already been encountered during the previous phase of the search. This letter analyzes the use of persistent dynamic sets for this purpose and discusses the advantages of this option with respect to popular but less efficient realizations. In particular, when combined with hashing, the method complexity per search iteration is of $O(L)$ average-case time and $O(1)$ amortized space, when the search space is given by $L$-bit binary strings. A concrete realization of the abstract data type through a C++ class is presented. The obtained memory occupation and timing results are analyzed for selected ``dictionary'' benchmark tasks and for the use of the structure to support history--sensitive heuristic algorithms.


BB2003a
Mauro Brunato and Roberto Battiti
PILGRIM: A Location Broker and Mobility-Aware Recommendation System
Proceedings of PerCom2003 the first IEEE Annual Conference on Pervasive Computing and Communications - Fort Worth (TX), USA, March 2003, edited by Das S., March 23-26, 2003. IEEE Computer Society, p. 265-272. URL : http://www.percom.org/ 
Digital version available: percom2003.pdf
Abstract: Mobile computing adds a mostly unexplored dimension to data mining: user's position is a relevant piece of information, and recommendation systems, selecting and ranking links of interest to the user, have the opportunity to take location into account. In this paper, a mobility-aware recommendation system that considers the location of the user to filter recommended links is proposed. To avoid the potential problems and costs of insertion by hand, a new middleware layer, the location broker, maintains a historic database of locations and corresponding links used in the past and develops models relating resources to their spatial usage pattern. These models are used to calculate a preference metric when the current user is asking for resources of interest. Mobility scenarios are described and analyzed in terms of possible user requirements. The features of the PILGRIM mobile recommendation system are outlined together with a preliminary experimental evaluation of different metrics.


BCGS2003
Roberto Battiti, Marco Conti, Enrico Gregori, Mikalai Sabel
Price-based Congestion-Control in Wi-Fi Hot Spots
Proceedings, WiOpt'03 March 3-5, 2003, INRIA Sophia-Antipolis, France.
Digital version available: Battiti26-wiopt.pdf
Abstract: Wireless networks are now proliferating due to the success of the IEEE 802.11b protocol, also known as Wi-Fi (Wireless Fidelity). A Wi-Fi network is characterized by a set of base stations (also called access points) placed throughout the environment and connected to the traditional wired LANs. This technology allows nomadic users a broadband access to the Internet if they are in the transmission range of an access point. A new business model, named Wi-Fi Hot Spots, is now emerging to exploit the potentialities of this technology. A hot spot is a critical business area, e.g., airports, stations, hotels, where users can have wireless access by subscribing a contract with the hot spot operator, or with a wireless Internet service provider (WISP). Due to the random access nature of the Wi-Fi technology, if the number of users connected to the same access point increases, the QoS experienced may quickly degrade. This generates complains from the users that, as a consequence, may change their WISP. In order to be competitive, a Wi-Fi hot spot operator needs simple and effective mechanisms to control the congestion therefore guaranteeing the QoS, and (at the same time) maximizing his/her revenues. In this paper we present and evaluate a price-based policy for the access control in a Wi-Fi hot spot. Our policy, named Price-based Congestion Control (PCC), controls the hot spot traffic by dynamically determining the access cost as a function of the current load in the hot spot. We develop a theoretical framework to compute for any load condition the access cost to maintain the hot spot in its optimal operating point, for any load condition. The effectiveness and robustness of the PCC policy has been evaluated by simulating a Wi-Fi hot spot. Both in saturated and notsaturated conditions the PCC policy provides a better channel utilization than the legacy Wi-Fi policy.


AAA2003
Roberto Battiti, Alessandro Villani, and Thang Le Nhat
Neural network model for intelligent networks: deriving the location from signal patterns"
Proceedings of The First Annual Symposium on Autonomous Intelligent Networks and Systems UCLA, May 8-9, 2002
Digital version available: ucla2002.pdf
Abstract: The knowledge of the location of a mobile terminal can be used to reduce the cognitive burden on the users in context-aware systems and it is a crucial information for routing in ad-hoc networks and for optimizing the topology in order to minimize the energy consumption of the nodes. The strengths of the RF signals arriving from more access points are related to the position (location fingerprinting), but the complexity of the inverse problem to derive the position from the signals and the lack of complete information, motivate to consider flexible models based on a network of functions (neural networks), developed through a supervised learning strategy. The advantage of the method is that it does not require ad-hoc infrastructure in addition to the wireless LAN, while the flexible modelling and learning capabilities of neural networks achieve small errors in determining the position, are amenable to incremental improvements, and do not require the detailed knowledge of the access point locations and of the building characteristics. The system does not participate in an active manner to determine the position, therefore guaranteeing a complete privacy. Experimental results and comparisons with alternative techniques are presented and discussed.


BBS2002b
MAURO BRUNATO, ROBERTO BATTITI, ELIO SALVADORI
Load Balancing in WDM Networks through Adaptive Routing Table Changes.
in E. GREGORI, M. CONTI, A.T. CAMBELL, G. OMIDYAR, M. ZUKERMAN, (editors) - NETWORKING 2002 (Pisa, May 2002), Lecture Notes in Computer Science 2345, Springer, pp. 289-300, 2002.
Digital version available: Networking.ps, Networking.pdf ,
Abstract: In this paper we develop a Load Balancing algorithm for IP-based Optical Networks. The considered networks are based on a routing protocol where the next hop at a given node depends only on the destination of the communication. Our algorithm (RSNE - Reverse Subtree Neighborhood Exploration) performs at each iteration a basic change of a single entry in a routing table in order to minimize the disruption of the network. We study the performance of our algorithm in realistic networks under static and dynamic traffic scenarios. Simulation results show a rapid reduction of the congestion for static networks and a performance of the incremental scheme while tracking a changing traffic matrix comparable to the complete reoptimization of the traffic.


BK2002
MAURO BRUNATO, CSABA KISS KALLó
Transparent Location Fingerprinting for Wireless Services.
Atti del Workshop Med-hoc-net (Hotel Chia Laguna (CA), 4-6 settembre 2002)
Digital version available: MedHocNet.ps , MedHocNet.pdf ,
Abstract: Detecting the user location is crucial in a wireless environment, not only for the choice of first-hop communication partners, but also for many auxiliary purposes: Quality of Service (availability of information in the right place for reduced congestion/delay, establishment of the optimal path), energy consumption, automated insertion of location-dependent info into a web query issued by a user (for example a tourist asking informations about a monument or a restaurant, a fireman approaching a disaster area). The technique we propose in our investigation tries to meet two main goals: transparency to the network and independence from the environment. A user entering an environment (for instance a wireless-networked building) shall be able to use his own portable equipment to build a personal map of the environment without the system even noticing it. Preliminary tests allow us to detect position on a map with an average uncertainty of two meters when using information gathered from three IEEE802.11 access points in an indoor environment composed of many rooms on a 625sqm area. Performance is expected to improve when more access points will be exploited in the test area. Implementation of the same techniques on Bluetooth are also being studied.


BBS2002
Mauro Brunato, Roberto Battiti and Elio Salvadori
Load Balancing in WDM Networks through Adaptive Routing Table Changes.
Planet-IP & Nebula Joint Workshop, Courmayeur, January 9-11, 2002
PostScript available: cour.ps
BBS2001
Mauro Brunato, Roberto Battiti and Elio Salvadori
Load Balancing in WDM Networks through Adaptive Routing Table Changes.
Technical Report Universita' di Trento, Dip. di Matematica, December 2001
PostScript available: BBS2001-Routing.pdf

Abstract: In this paper we develop Load Balancing algorithms for IP-based Optical Networks. The considered networks are based on a routing protocol where the next hop at a given node depends only on the destination of the communication. Our algorithm (RSNE - Reverse Subtree Neighborhood Exploration) performs at each iteration a basic change in the network by reconfiguring only a single entry in the routing table of a single node. We study the performance of our algorithm in realistic networks under static and dynamic traffic scenarios. Simulation results show a rapid reduction of the congestion for static networks. The performance of the incremental scheme while tracking a changing traffic matrix is comparable to that obtainable through the complete re-optimization of the traffic.


BB2001
R. Battiti and M. Brunato.
A Multistart Randomized Greedy Algorithm for Traffic Grooming on Mesh Logical Topologies. in "Next Generation Optical Network Design and Modelling", edited by Andrea Bianco and Fabio Neri, Kluwer Academic Publishers, 2003, pag. 417 -- 430.
(IFIP INTERNATIONAL FEDERATION FOR INFORMATION PROCESSING : Volume 242
Proceedings of ONDM2002 Optical Network Design and Modelling 2002, Torino, Italy, February 2002)
Preprint available: BB2001-Grooming.pdf

Abstract: In this paper we consider a logical topology design problem on DWDM optical networks where the traffic is quantized at sub-wavelength resolution and the critical factor to determine the fitness of a solution is the number of lightpaths required, that is proportional to the number of hardware modules to handle the traffic. The problem has been shown to be NP-hard. We review some of the previous work in the field, examine a number of regular but unsatisfactory solutions and describe a greedy-based iterated heuristic belonging to the GRASP family to minimize the number of lightpaths. At the end we present some experimental results that compare our GRASP heuristic with other greedy-based methods and with regular topologies.


BB2001b
R. Battiti and M. Brunato.
Reactive search for traffic grooming in WDM netwoks.
Evolutionary Trends of the Internet , IWDC 2001, Taormina, S. Palazzo (Ed.), Lecture Nites in Computer Science LNCS 2170, pp. 56--66, 2001.
PostScript available: BB2001-Rings.ps

Abstract: In this paper the Reactive Local Search (RLS) heuristic is proposed for the problem of minimizing the number of expensive Add-Drop multiplexers in a SONET or SDH optical network ring, while respecting the constraints given by the overall number of fibers and the number of wavelengths that can carry separate information on a fiber. RLS complements local search with a history-sensitive feedback loop that tunes the prohibition parameter to the local characteristics of a specific instance. Simulation results are reported to highlight the improvement in ADM cost when RLS is compared with greedy algorithms used in the recent literature.


ALE2001
R. Battiti, A. Bertossi, and S. Martello (Eds.)
Special issue:
Proceedings of the First Conference on Algorithms and Experiments (ALEX98), Trento, Italy, 1998.
Discrete Applied Mathematics, Vol. 110, No. 1, pp. 1-84, 2001


BPCLIQUE
R. Battiti and M. Protasi.
Reactive local search for the maximum clique problem.
Algorithmica , April 2001, vol. 29, no. 4, pag. 610--637
Abstract
Digital version available: rls-algorithmica.ps, (gzipped) rls-algorithmica.ps.gz .

Abstract: A new Reactive Local Search (RLS) algorithm is proposed for the solution of the Maximum-Clique problem. RLS is based on local search complemented by a feedback (memory-based) scheme to determine the amount of diversification. The reaction acts on the single parameter that decides the temporary prohibition of selected moves in the neighborhood, in a manner inspired by Tabu Search. The performance obtained in computational tests appears to be significantly better with respect to all algorithms tested at the the second DIMACS implementation challenge. The worst-case complexity per iteration of the algorithm is O { max ( n, m ) } where n and m are the number of nodes and edges of the graph. In practice, when a vertex is moved, the number of operations tends to be proportional to its number of missing edges and therefore the iterations are particularly fast in dense graphs.


ENC2001
R. Battiti
Maximum satisfiability problem, MAX-SAT
In "Encyclopedia of Optimization" (C.A. Floudas and P.M. Pardalos, Eds) Kluwer Academic Publishers (2001) Vol. 3, pp. 266-272.
Digital version available: encyclopedia-mar2000.ps


BBB99
R. Battiti, A. A. Bertossi, and M. A. Bonuccelli.
Assigning codes in wireless networks: bounds and scaling properties.
Wireless Networks , Vol. 5 (1999) pp. 195-209.
PostScript available: codeass.ps

Abstract: Different types of interferences (``collisions'') can occur in multihop packet radio networks, caused by the time overlap of more packets. In particular, a direct (or primary) collision arises by the (quasi) simultaneous transmission of two stations which can hear each other, while a hidden (or secondary) collision can be caused by two stations that cannot hear each other, but are both received by the same destination. In the Code Division Multiple Access (CDMA) framework, the collisions are eliminated by assigning orthogonal codes to stations, a problem equivalent to that of coloring graphs associated to the physical network. In this paper we present new algorithms for two versions of the problem (hidden and primary collision avoidance -- HP-CA -- or hidden collision avoidance only -- H-CA). In particular, exact algorithms for special topologies and heuristics for general topologies are proposed. The schemes show better average results with respect to existing alternatives. Furthermore, the gap between the heuristic solution, the lower bounds obtained from the maximum-clique problem, and the exact solution obtained by branch \& bound is investigated in the different contexts. A scaling law is then proposed to explain the relations between the number of codes needed in Euclidean networks with different station density and connection distance, and the substantial difference between the two versions HP-CA and H-CA of the problem is investigated by studying the probabilistic distribution of connections as a function of the distance, and the asymptotic size of the maximum cliques. Finally, the distributed and dynamic realization of the algorithms is discussed. An experimental evaluation of the methods is executed on randomly generated Euclidean networks modeling the real-world problem.


BB99
R. Battiti and A. Bertossi.
Greedy, Prohibition, and Reactive Heuristics for Graph-Partitioning
IEEE Transactions on Computers , Vol. 48, Number 4, April 1999, pp.361-385.
PDF proofs: gp.pdf

Digital version available: gp.ps

Abstract: New heuristic algorithms are proposed for the Graph Partitioning problem. A greedy construction scheme with an appropriate tie--breaking rule (MIN-MAX-GREEDY) produces initial assignments in a very fast time. For some classes of graphs, independent repetitions of MIN-MAX-GREEDY are sufficient to reproduce solutions found by more complex techniques. When the method is not competitive, the initial assignments are used as starting points for a prohibition-based scheme, where the prohibition parameter is chosen in a randomized and reactive way, with a bias toward more successful choices in the previous part of the run. The relationship between prohibition-based diversification (Tabu Search) and the well-know variable-depth Kernighan--Lin algorithm is discussed. Detailed experimental results are presented on the same benchmark suite used in previous papers, showing a better performance for equivalent or smaller computing times.


WINET2000
R. Battiti, A. Bertossi and M. Brunato.
Cellular channel assignment: a new localized and distributed strategy
Mobile Networks and Applications , No. 6, pag. 493-500, 2001.
Digital version available: monet2001.ps

Abstract: As the use of mobile communications systems grows, the need arises for new and more efficient channel allocation techniques. The total number of available channels on a real-world network is in fact a scarce resource, and many assignment heuristics su er from a clear lack of (this is the case of Fixed Channel Allocation), or from high computational and communication complexity (as with channel borrowing techniques). Performance can be improved by representing the system with an objective function whose minimum is associated with a good con guration; the various constraints appear as penalty terms in the function. The problem is thus reduced to the search for a minimum, that is often performed via heuristic algorithms like Hop eld neural networks, simulated annealing or reinforcement learning. These strategies usually require a central process to have global information and decide for all cells. We consider an objective-function formulation of the channel assignment problem that has been previously solved by search heuristics; we prove that the search time for the global minimum of the objective function is O(n log n), and therefore there is no need for search techniques. Finally we show that the algorithm that arises from this formulation can be modi ed so that global knowledge and synchronization are no longer required, and we give its distributed version. By simulating a cellular network with mobile hosts on a hexagonal cell pattern with uniform call distribution, we show that our technique actually performs better than the best known algorithms.


IEEETVT2007
Li, B.; Battiti, R.; Fang, Y.
Achieving Optimal Performance by Using the IEEE 802.11 MAC Protocol With Service Differentiation Enhancements
IEEE Transactions on Vehicular Technology , Vol. 56, Issue. 3, pag. 1374 - 1387 , May 2007.
Digital version available: vt2007.pdf (DOI Digital Object Identifier : 10.1109/TVT.2007.895565 )

Abstract: Wireless local area networks are currently evolving to support adequate degrees of service differentiation. Work is in progress to define an enhanced version of the IEEE 802.11 distributed coordination function, which is capable of supporting quality of service for multimedia traffic at the medium access control layer. In this paper, we aim at gaining insight into one mechanism to differentiate among traffic categories, i.e., differentiating the minimum contention window sizes according to the priority of different traffic categories. The contribution of this paper is the analysis of the optimal operation point where maximum throughput can be achieved. Through the analysis, we answer some fundamental questions about the existence and uniqueness of the optimal operation point, about the maximum system throughput, about the existence of simple rules to decide if the system operates under the optimal state or not, and about procedures to lead the system to the optimal operation point. The other contribution is the proposal of a simple adaptive scheme that makes the system operate under the optimal operation point and, at the same time, achieve target service differentiation between different traffic flows. The results that are obtained in this paper are relevant to both theoretical research and implementations of real systems.


IEEETVT2000
R. Battiti, A. Bertossi and D. Cavallaro.
A randomized saturation degree heuristic for channel assignment in cellular radio networks
IEEE Transactions on Vehicular Technology , Vol. 50, No. 2, pag. 364-374, March 2001.
Digital version available: VehicularTechnology2000.ps

Abstract: In this paper we investigate the channel assignment problem, that is the problem of as- signing channels (codes) to the cells of a cellular radio network so as to avoid interference and minimize the number of channels used. The problem is formulated as a generalization of the graph coloring problem. We consider the Saturation Degree (SD) heuristic, rst pro- posed as a technique for solving the graph coloring problem, which was already successfully used for code assignment in Packet Radio Networks. We give a new version of this heuristic technique for cellular radio networks, called Randomized Saturation Degree (RSD), based on node ordering and randomization. Furthermore we improve the solution given by RSD by means of a local search technique. Experimental results show the e ectiveness of the heuristic both in terms of solution quality and computing times.
Keywords: channel assignment problem (CAP), cellular network, heuristic, graph color- ing, local search.


WSDAAL00
Roberto Battiti, Alan A. Bertossi, Mauro Brunato.
Distributed Saturation Degree Methods For Code Assignment In Multihop Radio Networks
Workshop su Sistemi Distribuiti: Algoritmi, Architetture e Linguaggi (WSDAAL2000) Ischia (Napoli). 18-20 Settembre 2000.
Digital version available: wsdaal2000.ps
WSDAAL2000 - workshop site

Abstract: We present a new distributed algorithm for code assignment in a multihop radio network. The algorithm is based on the Saturation-Degree coloring scheme proposed in [Battiti,Bertossi,Bonuccelli,1999], which has proved better than earlier attempts at solving the problem. A crucial parameter of the proposed algorithm is the depth of the neighborhood that must be considered when a local decision must be taken. By tuning this parameter one can obtain a tradeo between the quality of the solution and the number of parallel passes and exchanged messages. We analyze the results of our simulation programs where the proposed algorithm is compared with its sequential version and with competitive schemes proposed in the literature.


SOFTCOM2000
Roberto Battiti, Alan A. Bertossi, Mauro Brunato.
Distributed Code Assignment in Multihop Radio Networks: Object-Oriented Software Simulations
Proceedings, International Conference on Software, Telecommunications and Computer Networks (SoftCom2000) Split- Rijeka, Croatia, Trieste - Venice, Italy, Oct 10-14, 2000. Vol I, pag. 157-165.
Digital version available: softcom2000.ps
SoftCom2000 - workshop site

Abstract: Code Assignment is one of the central problems in the management of mobile wireless networks, where a very precious resource (radio bandwidth) needs to be carefully shared among network nodes. As this problem has been shown to be NP­hard in every real world instance, no practical exact solution can be provided, and heuristic algorithms are being developed whose actual performance can hardly be calculated by theorical means; hence the development of heuristic schemes must always be accompanied by appropriate simulation software. In this paper we present a new distributed algorithm for code assignment in a multihop radio network. The algorithm is based on the Saturation­Degree coloring scheme proposed in [Battiti,Bertossi,Bonuccelli,1999], which has proved better than earlier attempts at solving the problem. A crucial parameter of the proposed algorithm is the depth of the neighborhood that must be considered when a local decision must be taken. By tuning this parameter one can obtain a tradeoff between the quality of the solution and the number of parallel passes and exchanged messages. We analyze the results of our C++ simulation programs where the proposed algorithm is compared with its sequential version and with competitive schemes proposed in the literature. Furthermore, to help analyzing the behavior of our distributed technique, we provide a graphical simulation environment written in Java.
Keywords: Saturation Degree, Distributed Computing, Wireless Networks, Software for Telecommunications


WSDAAL99
R. Battiti, A. Bertossi and D. Cavallaro.
A randomized saturation degree heuristic for channel assignment in cellular radio networks
Proceedings Quarto Workshop su Sistemi Distribuiti: Algoritmi, Architetture e Linguaggi (WSDAAL'99) , Fonte Cerreto, l'Aquila, Italy, Sep 13-15, 1999, pp. 96-101.
Digital version available: wsdaal99.ps


UTM554
R. Battiti, A. Bertossi and A. Cappelletti.
Multilevel Reactive Tabu Search for Graph Partitioning
Preprint UTM 554, Maggio 1999, Dip. di Matematica, Università di Trento.
Digital version available: UTM-554.ps


UTM555
R. Battiti, A. Bertossi and D. Cavallaro.
A randomized saturation degree heuristic for channel assignment in cellular radio networks
Preprint UTM 555, Maggio 1999, Dip. di Matematica, Università di Trento.
Digital version available: UTM-555.ps


BBB98
R. Battiti, A. A. Bertossi, and M. Brunato.
Cellular channel assignment: a new localized and distributed algorithm
Preprint UTM-524, Dip. di Matematica, Univ. di Trento, Italy, Jan 1998
MONET special issue on Dial M for Mobility, 1999
Digital version available (local cache): cellular-preprint.ps


BaPr98
R. Battiti and M. Protasi.
Approximate Algorithms and Heuristics for MAX-SAT
Handbook of Combinatorial Optimization, Vol 1, 1998, 77-148, Kluwer Academic Publishers.
Digital version available: max-sat.pdf

Contents:
1 Introduction ... 78
1.1 Notation and graphical representation ... 79
2 Resolution and Linear Programming ... 80
2.1 Resolution and backtracking for SAT ... 80
2.2 Integer programming approaches ... 83
3 Continuous approaches ... 85
3.1 An interior point algorithm ... 85
3.2 Continuous unconstrained optimization ... 86
4 Approximate algorithms ... 86
4.1 Definitions and basic results ... 87
4.2 Johnson's approximate algorithms ... 91
4.3 Randomized algorithms for MAX W--SAT ... 99
4.3.1 A randomized $1/2$--approximate algorithm for MAX W--SAT ... 99
4.3.2 A randomized $3/4$-approximate algorithm for MAX W--SAT ... 102
4.3.3 A variant of the randomized rounding technique ... 107
4.4 Another $3/4 $--approximate algorithm by Yannakakis ... 110
4.5 Approximate solution of MAX W--SAT : improvements ... 115
4.6 Negative results about approximability ... 116
5 A different MAX--SAT problem and completeness results ... 117
6 Local search ... 118
6.1 Quality of local optima ... 120
6.2 Non-oblivious local optima ... 122
6.2.1 An example of non-oblivious search ... 124
6.3 Local search satisfies most 3--SAT formulae ... 125
6.4 Randomized search for 2--SAT (Markov processes) ... 126
7 Memory-less Local Search Heuristics ... 128
7.1 Simulated Annealing ... 128
7.2 Gsat with ``random noise'' strategies ... 129
7.3 Randomized Greedy and Local Search (Grasp) ... 130
8 History-sensitive Heuristics ... 132
8.1 Prohibition-based Search: TS and Samd ... 132
8.2 Hsat and ``clause weighting'' ... 133
8.3 Reactive Search ... 133
8.3.1 The Hamming-Reactive Tabu Search (H-RTS) algorithm ... 135
9 Experimental analysis and threshold effects ... 136
9.1 Models ... 137
9.2 Hardness and threshold effects ... 138


BBR97
R. Battiti, A. A. Bertossi, and R. Rizzi.
Randomized Greedy Algorithms for the Hypergraph Partitioning Problem Randomization Methods in Algorithm Design
Edited by: Panos Pardalos, Sanguthevar Rajasekaran, and Jose Rolim
DIMACS Series in Discrete Mathematics and Theoretical Computer Science
Vol. 43, 21--35,
American Mathematical Society, 1998
Digital version available: dimacs-randomized.pdf dimacs-randomized.ps

Abstract: We propose a series of randomized greedy construction schemes for the hypergraph partitioning problem. While the final results are inferior to those obtained by recent multi-level methods, the advantages of our greedy schemes are their simplicity and low computational complexity. The best greedy algorithms considered obtain low cut values and large standard deviations of the results. Therefore, when independent repetitions are considered, the quality of the best solution greatly improves and, in some cases, it is superior to the variable-depth Fiduccia-Mattheyses (FM) algorithm, for smaller CPU times. Furthermore, the algorithms can be used as building blocks in more complex schemes. For example, we successfully employ our greedy schemes to produce initial partitions for improvement-based heuristics. In particular, if FM is run starting from partitions generated by our greedy schemes, instead of random initial solutions, a significant improvement of the average solution quality is achieved for comparable computation times.


BBB97
R. Battiti, A. A. Bertossi, and M. Brunato.
Cellular channel assignment: comparing and simplifying heuristics
Proceedings of the IEEE/AMC Workshop Dial M for Mobility , (Discrete algorithms and methods for mobile computing and communications) Budapest, Oct 1, 1997
Digital version available (local cache): cellular.ps


BP97
R. Battiti and M. Protasi.
Reactive Local Search for Maximum Clique
Proceedings of the Workshop on Algorithm Engineering (WAE'97), Ca' Dolfin, Venice, Italy, Sep 11-13, 1997, pp. 74-82


BB97
R. Battiti and A. Bertossi.
Differential Greedy for the 0--1 Equicut Problem
Network Design: Connectivity and Facilites Location Edited by D.Z. Du and P.M. Pardalos, American Mathematical Society. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol 40, pp. 3--21, 1998.
Digital version available: gp-dimacs.ps

Abstract: Given the success of recent greedy schemes with tie-breaking rules proposed by the authors, this paper extends the investigation by considering different greedy approaches for the graph bi-partitioning problem. In particular, a new method is proposed (DIFFGREEDY) that ameliorates in a significant way the performance of the previously proposed MINMAXGREEDY, while requiring less computation. The computational complexity is demonstrated to be O(|E|) , E being the edge set of the graph. Experimental results are presented for a large sample of two classes of randomly generated graphs, one with a connection probability independent of the vertices, the second one with a two-dimensional geometric structure. Remarkably enough, the cut sizes obtained through independent repetitions are close to, and in some cases better than the cut sizes obtained by more sophisticated techniques based on standard greedy construction followed by local search with prohibition-based diversification (Tabu Search), for comparable running times.


BP97
R. Battiti and M. Protasi.
Reactive Search, a history-sensitive heuristic for MAX-SAT
ACM Journal of Experimental Algorithmics , Vol. 2, Paper 2, 1997.
Subscribers to JEA can access the paper and software at: http://www.jea.acm.org/1997/BattitiReactive/
PostScript of previous preprint available: reactive-sat.ps
Vol2Nbr2.tar (tar archive of C++ code for MAX-SAT)
Abstract: The Reactive Search (RS) method proposes the integration of a simple history-sensitive (machine learning) scheme into local search for the on-line determination of free parameters. In this paper a new RS algorithm is proposed for the approximated solution of the Maximum Satisfiability problem: a component based on local search with temporary prohibitions (Tabu Search) is complemented with a reactive scheme that determines the appropriate value of the prohibition parameter by monitoring the Hamming distance along the search trajectory. The proposed algorithm (H-RTS) can therefore be characterized as a dynamic version of Tabu Search. In addition, the non-oblivious functions recently introduced in the framework of approximation algorithms are used to discover a better local optimum in the initial part of the search. The algorithm is developed in two phases. First the bias-diversification properties of individual candidate components are analyzed by extensive empirical evaluation, then a reactive scheme is added to the winning component, based on Tabu Search. The final tests on a benchmark of random MAX--3--SAT and MAX--4--SAT problems demonstrate the superiority of H-RTS with respect to alternative heuristics.


BP99
R. Battiti and M. Protasi.
Reactive Local Search techniques for the Maximum k-Conjunctive Constraint Satisfaction Problem.
Discrete Applied Mathematics , 96-97 (1999), pp. 3--27.
Digital version available at ccsp.ps.


BPa
R. Battiti and M. Protasi.
Reactive search, a history-based heuristic for MAX-SAT.
Workshop on Satisfiability, Siena, Italy, 1996.
Digital version available at hrts-sat-siena96.ps.


BPb
R. Battiti and M. Protasi.
Solving MAX-SAT with non-oblivious functions and history-based heuristics.
In: Dingzhu Du and Jun Gu and Panos M. Pardalos (Eds.)
Satisfiability Problem: Theory and Applications ,
DIMACS: Series in Discrete Mathematics and Theoretical Computer Science, no. 35.
American Mathematical Society, Association for Computing Machinery, 1997, pag. 649--667.
Digital version available: nrts-sat-dimacs96.ps.


Bat96a
R. Battiti.
Reactive search: Toward self-tuning heuristics.
In V. J. Rayward-Smith, editor, Modern Heuristic Search Methods, chapter 4, pages 61--83. John Wiley and Sons Ltd, 1996.
Digital version available: adt-book-chapter.ps.

Abstract: Local (neighborhood) search can be guided to go beyond local minima through meta-heuristic methods that use the information obtained in the previous part of the run. The Reactive Search (RS) method proposes the integration of simple memory-based feedback schemes in local search for the on-line determination of free parameters, therefore endowing the algorithm with the flexibility needed to cover a wide spectrum of problems but avoiding a human trial-and-error adjustment. In particular, in the Reactive Tabu Search (RTS) algorithm a simple feedback scheme influences the value of the prohibition parameter in Tabu Search, so that a balance of exploration versus exploitation is obtained that is appropriate for the local characteristics of the task. This paper summarizes the Reactive Search framework, reviews RTS and its applications, and presents novel results about the behavior of different Tabu Search schemes when escaping from a local attractor.


BT95c
R. Battiti and G. Tecchiolli.
Training neural nets with the reactive tabu search.
IEEE Transactions on Neural Networks, 6(5):1185--1200, 1995.
PDF available: rts-nn.pdf.

Abstract: In this paper the task of training sub-symbolic systems is considered as a combinatorial optimization problem and solved with the heuristic scheme of the Reactive Tabu Search (RTS) proposed by the authors and based on F. Glover's Tabu Search. An iterative optimization process based on a ``modified greedy search'' component is complemented with a meta-strategy to realize a discrete dynamical system that discourages limit cycles and the confinement of the search trajectory in a limited portion of the search space. The possible cycles are discouraged by prohibiting (i.e., making tabu) the execution of moves that reverse the ones applied in the most recent part of the search, for a prohibition period that is adapted in an automated way. The confinement is avoided and a proper exploration is obtained by activating a diversification strategy when too many configurations are repeated excessively often. The RTS method is applicable to non-differentiable functions, it is robust with respect to the random initialization and effective in continuing the search after local minima. The limited memory and processing required make RTS a competitive candidate for special-purpose VLSI implementations. We present and discuss four tests of the technique on feedforward and feedback systems.


BT94b
R. Battiti and G. Tecchiolli.
The reactive tabu search.
ORSA Journal on Computing, 6(2):126--140, 1994.
Digital version available: TheReactiveTabuSearch.PDF.

Abstract: We propose an algorithm for combinatorial optimization where an explicit check for the repetition of configurations is added to the basic scheme of Tabu search. In our Tabu scheme the appropriate size of the list is learned in an automated way by reacting to the occurrence of cycles. In addition, if the search appears to be repeating an excessive number of solutions excessively often, then the search is diversified by making a number of random moves proportional to a moving average of the cycle length. The reactive scheme is compared to a "strict" Tabu scheme, that forbids the repetition of configurations and to schemes with a fixed or randomly varying list size. From the implementation point of view we show that the Hashing or Digital Tree techniques can be used in order to search for repetitions in a time that is approximately constant. We present the results obtained for a series of computational tests on a benchmark function, on the 0-1 Knapsack Problem, and on the Quadratic Assignment Problem.


BT94c
R. Battiti and G. Tecchiolli.
Simulated annealing and tabu search in the long run: a comparison on qap tasks.
Computer and Mathematics with Applications, 28(6):1--8, 1994.
Digital version available: SimulatedAnnealing.PDF.

Abstract: Simulated Annealing (SA) and Tabu Search (TS) are compared on the Quadratic Assignment Problem. A recent work on the same benchmark suite argued that SA could achieve a reasonable solution quality with fewer function evaluations than TS. The discussion is extended by showing that the conclusions must be changed if the task is hard or a very good approximation of the optimal solution is desired, or if CPU time is the relevant parameter. In addition, a recently proposed version of TS (the Reactive Tabu Search) solves the problem of finding the proper list size with an automatic memory-based reaction mechanism.


ABL+95b
G. Anzellotti, R. Battiti, I. Lazzizzera, G. Soncini, A. Zorat, A. Sartori, G. Tecchiolli, and P. Lee.
Totem: a highly parallel chip for triggering applications with inductive learning based on the reactive tabu search.
International Journal of Modern Physics C, 6(4):555--560, 1995.
Digital version available: aihenp-95. ps.

Abstract: The training of a Multi-Layer Perceptron (MLP) classifier is considered as a Combinatorial Optimization task and solved with the Reactive Tabu Search (RTS) method. RTS needs only forward passes (no derivatives), and it does not need high precision in the network parameters. A special-purpose VLSI architecture has been developed to take advantage of the limited memory and processing requirements of RTS: the final system realizes a very close coupling of hardware and training algorithm. The RTS algorithm and the design of the VLSI chip are discussed, together with the operational characteristics of TOTEM and some preliminary training and generalization tests on triggering tasks.


ABL+5a
G. Anzellotti, R. Battiti, I. Lazzizzera, P. Lee, A. Sartori, G. Soncini, G. Tecchiolli, and A. Zorat.
Totem: a highly parallel chip for triggering applications with inductive learning based on the reactive tabu search.
In AIHENP95, Pisa, IT, April 1995.


BC94a
R. Battiti and A. M. Colla.
Democracy in neural nets: Voting schemes for accuracy.
Neural Networks, 7(4):691--707, 1994.
Digital version available: DemocracyInNeuralNets.PDF.


BST+95
R. Battiti, A. Sartori, G. Tecchiolli, Tonella, and A. Zorat.
Neural compression: an integrated approach to EEG signals.
In J. Alspector, R. Goodman, and T. X. Brown, editors, International Workshop on Applications of Neural Networks to Telecommunications (IWANNT*95), pages 210--217, Stockholm, Sweden, May 1995.


BLST94b
R. Battiti, P. Lee, A. Sartori, and G. Tecchiolli.
Totem: A digital processor for neural networks and reactive tabu search.
In Fourth International Conference on Microelectronics for Neural Networks and Fuzzy Systems, MICRONEURO 94, pages 17--25, Torino, IT, 1994. IEEE Computer Society Press. Preprint UTM 436-June 1994, Università di Trento, IT.


BLST94a
R. Battiti, P. Lee, A. Sartori, and G. Tecchiolli.
Combinatorial optimization for neural nets: Rts algorithm and silicon.
Technical report, Dept. of Mathematics, University of Trento, IT, 1994. Preprint UTM 435.


BLST95
R. Battiti, P. Lee, A. Sartori, and G. Tecchiolli.
Special-purpose parallel architectures for high-performance machine learning.
In High Performance Computing and Networking, Milano, IT, 1995. Preprint UTM 445, December 1994, Università di Trento, IT.


BG92
R. Battiti and G.Tecchiolli.
Parallel biased search for combinatorial optimization: Genetic algorithms and tabu.
Microprocessor and Microsystems, 16:351--367, 1992.
Digital version available: ParallelBiasedSearchForCombinatorialOptimization.PDF.


BT94a
R. Battiti and G. Tecchiolli.
Learning with first, second, and no derivatives: a case study in high energy physics.
Neurocomputing, 6:181--206, 1994.
Digital version available: LearningwithFirstSecond.PDF.

Abstract: In this paper different algorithms for training multi-layer perceptron architectures are applied to a significant discrimination task in High Energy Physics. The One Step Secant technique is compared with On-Line Backpropagation, the 'Bold Driver' batch version and Conjugate Gradient methods. In addition, a new algorithm (Affine Shaker) is proposed that uses stochastic search based on function values and affine transformations of the local search region. Although the Affine Shaker requires more CPU time to reach the maximum generalization, the technique can be interesting for special-purpose VLSI implementations and for non-differentiable functions.


BT96
R. Battiti and G. Tecchiolli.
The continuous reactive tabu search: blending combinatorial optimization and stochastic search for global optimization.
Annals of Operations Research -- Metaheuristics in Combinatorial Optimization, 63:153--188, 1996.
Digital version available: TheContinuousReactiveTabuSearch.PDF .

Abstract: A novel algorithm for the global optimization of functions (C-RTS) is presented, in which a combinatorial optimization method cooperates with a stochastic local minimizer. The combinatorial optimization component, based on the Reactive Tabu Search recently proposed by the authors, locates the most promising ``boxes,'' where starting points for the local minimizer are generated. In order to cover a wide spectrum of possible applications with no user intervention, the method is designed with adaptive mechanisms: the box size is adapted to the local structure of the function to be optimized, the search parameters are adapted to obtain a proper balance of diversification and intensification. The algorithm is compared with some existing algorithms, and the experimental results are presented for a suite of benchmark tasks.


POSITION96
Roberto Battiti
Machine learning methods for parameter tuning in heuristics
5th DIMACS Challenge Workshop: Experimental Methodology Day, Oct 30, 1996, Rutgers University
Digital version available: position-paper96up.pdf
position-paper96up.htm
Abstract:


BT95b
R. Battiti and G. Tecchiolli.
Local search with memory: Benchmarking RTS.
Operations Research Spektrum, 17(2/3):67--86, 1995.
Digital version available: LocalSearchWithMemory.PDF.

Abstract: The purpose of this work is that of presenting a version of the Reactive Tabu Search method (RTS) that is suitable for constrained problems, and that of testing RTS on a series of constrained and unconstrained Combinatorial Optimization tasks. The benchmark suite consists of many instances of the N-K model and of the Knapsack problem with various sizes and difficulties, defined with portable random number generators. The performance of RTS is compared with that of Repeated Local Minima Search, Simulated Annealing, Genetic Algorithms, and Neural Networks. In addition, the effects of different hashing schemes and of the presence of a simple `aspiration' criterion in the RTS algorithm are investigated.


Bat91
R. Battiti.
Real-time multi-scale vision on multi-computers.
Concurrency, Practice and Experience, 3(2):55--88, 1991.


Bat92
R. Battiti.
First- and second-order methods for learning: Between steepest descent and newton's method.
Neural Computation, 4(2):141--166, 1992.
Digital version available: FirstSecondOrderMethodsForLearning.PDF.


Bat93
R. Battiti.
The reactive tabu search for machine learning.
In G. Mauri, editor, Quarto Workshop del Gruppo AI*IA di Interesse Speciale su Apprendimento Automatico, pages 41--55, Milano, IT, June 1993.


Bat94
R. Battiti.
Using the mutual information for selecting features in supervised neural net learning.
IEEE Transactions on Neural Networks, 5(4):537--550, 1994.
PDF available: mutual-nn.pdf. Recently cited in BMC1 , BMC2.


BAK91
Roberto Battiti, Edoardo Amadli, Christof Koch.
Computing Optical Flow Across Multiple Scales: An Adaptive Coarse-to-Fine Strategy
International Journal of Computer Vision, 6(2):133-145, 1991.


Bat89
Roberto Battiti.
Accelerated Back-propagation Learning: Two Optimization Methods
Complex Systems , vol. 3, n. 4 (1989) pp. 331-342.
Digital version available: AcceleratedBackpropagationLearning.PDF.


Technical Reports DIT (local cache)

DIT-02-11
Brunato, Mauro and Battiti, Roberto and Salvadori, Elio
Dynamic load balancing in WDM Networks
Technical Report DIT-02-11, Informatica e Telecomunicazioni, Università degli Studi di Trento.
Digital version available: 11.pdf
Abstract:
DIT-02-83
Battiti, Roberto and Le, Nhat Thang and Villani, Alessandro
Location-aware computing: a neural network model for determining location in wireless LANs.
Technical Report DIT-0083, Informatica e Telecomunicazioni, Università degli Studi di Trento.
Digital version available: 83.pdf
Abstract: The strengths of the RF signals arriving from more access points in a wireless LANs are related to the position of the mobile terminal and can be used to derive the location of the user. In a heterogeneous environment, e.g. inside a building or in a variegated urban geometry, the received power is a very complex function of the distance, the geometry, the materials. The complexity of the inverse problem (to derive the position from the signals) and the lack of complete information, motivate to consider flexible models based on a network of functions (neural networks). Specifying the value of the free parameters of the model requires a supervised learning strategy that starts from a set of labeled examples to construct a model that will then generalize in an appropriate manner when confronted with new data, not present in the training set. The advantage of the method is that it does not require ad-hoc infrastructure in addition to the wireless LAN, while the flexible modeling and learning capabilities of neural networks achieve lower errors in determining the position, are amenable to incremental improvements, and do not require the detailed knowledge of the access point locations and of the building characteristics. A user needs only a map of the working space and a small number of identified locations to train a system, as evidenced by the experimental results presented.
DIT-02-86
Battiti, Roberto and Brunato, Mauro and Villani, Alessandro
Statistical Learning Theory for Location Fingerprinting in Wireless LANs.
Technical Report DIT-0086, Informatica e Telecomunicazioni, Università degli Studi di Trento.
Digital version available: 86.pdf
Abstract: In this paper, techniques and algorithms developed in the framework of statistical learning theory are analyzed and applied to the problem of determining the location of a wireless device by measuring the signal strengths from a set of access points (location fingerprinting). Statistical Learning Theory provides a rich theoretical basis for the development of models starting from a set of examples. Signal strength measurement is part of the normal operating mode of wireless equipment, in particular Wi-Fi, so that no custom hardware is required. The proposed techniques, based on the Support Vector Machine paradigm, have been implemented and compared, on the same data set, with other approaches considered in the literature. Tests performed in a real-world environment show that results are comparable, with the advantage of a low algorithmic complexity in the normal operating phase. Moreover, the algorithm is particularly suitable for classification, where it outperforms the other techniques.
DIT-02-92
Brunato, Mauro and Battiti, Roberto
PILGRIM: A Location Broker and Mobility-Aware Recommendation System
Technical Report DIT-02-92, Informatica e Telecomunicazioni, Università degli Studi di Trento.
Digital version available: 92.pdf
Abstract:
DIT-02-93
Brunato, Mauro and Battiti, Roberto and Villani, Alessandro and Delai, Andrea
A Location-Dependent Recommender System for the Web.
Technical Report DIT-02-93, Informatica e Telecomunicazioni, Università degli Studi di Trento.
Digital version available: 93.pdf
Abstract:
DIT-02-94
Li, Bo and Battiti, Roberto
A channel assignment and handoff strategy for mobile multimedia cellular communication systems with variable bandwidth support.
Technical Report DIT-02-94, Informatica e Telecomunicazioni, Università degli Studi di Trento.
Digital version available: 94.pdf
Abstract:
DIT-02-95
Salvadori, Elio and Battiti, Roberto
A Load Balancing Scheme for Congestion Control in MPLS Networks.
Technical Report DIT-02-95, Informatica e Telecomunicazioni, Università degli Studi di Trento.
Digital version available: 95.pdf
Abstract:
DIT-02-98
Elio Salvadori, Roberto Battiti, Mikalai Sabel
A Reactive Scheme for Traffic Engineering in MPLS Networks
Technical Report Technical Report DIT-02-098, Dipartimento di Informatica e Telecomunicazioni, Università degli Studi di Trento, Dec 2002.
Digital version available: 98.pdf
Abstract: In this paper we develop a new Traffic Engineering scheme for congestion control in MPLS networks based on a reactive mechanism. While most existing TE schemes to prevent network congestion rely on constraint-based routing (CBR), the proposed algorithm uses a local search technique where the basic move is the modification of the route for a single Label Switched Path (LSP). Two versions of the algorithm are proposed: in the first one, called FID, an already established LSP is rerouted when a certain level of network congestion is detected, while in the second, called LFID, it is rerouted when a new LSP request cannot be satisfied. Experiments under a dynamic traffic scenario show a reduced rejection probability especially with long-lived and bandwidth consuming connection requests, thus proving a better network resource utilization compared to existing CBR schemes in MPLS networks.


COLLA93
Anna Maria Colla
Soluzioni neuronali per problemi di pattern recognition
Automazione e strumentazione, Marzo 1993
Digital version available: colla.doc
Abstract: spiegazione divulgativa in italiano di lavori apparsi in inglese (citati nell'articolo) legati all'uso di reti neuronali per applicazioni industriali.

Last Invited Talks and Tutorials



(Back to Battiti Home Page)