Četvrtak, 01. septembar 2005. u 17h, sala 2, MI SANU:

Prof. Yuri Kochetov, Sobolev Institute of Mathematics, Novosibirsk, Russia
THE 2D RECTANGULAR BIN PACKING PROBLEM WITH IMPURITIES

Abstract: We consider the real-world two dimensional rectangular bin packing problem originating in the steel industry. The bins are inhomogeneous sheets with impurities. Each impure area is rectangle. For each bin we are given a set of impurities, size, and location of each impurity into the bin. We need to place the rectangular items into the minimal number of bins. The items have the attribute whether they can be located in the area with impurities. Overlaps of items are not allowed.
For solving this NP-hard problem we have developed a tailored Simulated Annealing algorithm (SA) based on the directed root tree encoding scheme. The scheme has linear decoding time if the maximal number of impurities per bin is a constant. The initial solution is built by a greedy algorithm which allows us to start SA with low temperature. Computational experiments show that the algorithm produces feasible solutions with small deviations from the lower bound within a few minutes.

Petak, 02. septembar 2005. u 14h, sala 2, MI SANU:

Dr. Zoran Obradović, Mathematical Institute SANU and Center for Information Science and Technology, Temple University, Philadelphia, PA
INTEGRATION OF DETERMINISTIC AND STATISTICAL ALGORITHMS FOR RETRIEVAL AND ANALYSIS OF GEOPHYSICAL PARAMETERS

Abstract: Current methods for the retrieval of geophysical information from satellite data are based on deterministic forward simulation algorithms. In this approach, physical models predict what the instruments will observe under possible atmospheric and reflective surface conditions. These predictions are then compared to observations, and the condition corresponding to the best prediction is assumed to hold. The drawbacks include high computational cost and the manual enhancements to the postulated physical models. We proposed a novel data mining based method for addressing these drawbacks by complementing deterministic models with computationally cheaper statistical algorithms that can exploit data of varying quality obtained from multiple sources. Statistical retrieval involves learning classification or regression mappings from observed attributes to corresponding geophysical parameters.
Our case study is devoted to improving efficiency and accuracy of aerosol optical thickness (AOT) retrievals by developing regression methods for learning a mapping from observation attributes to the corresponding parameters. We will first describe a statistical approach for exploiting multiple sources of remote sensing data illustrated on faster and more accurate AOT retrievals over the continental USA. Large test data is obtained from MISR (Multi-angle Imaging SpectroRadiometer) and MODIS (Moderate Resolution Imaging Spectrometer) instruments aboard Terra and Aqua satellites. Next, we will present a fusion of models approach that improved accuracy of MISR AOT retrievals over the continental USA by appropriately weighting global and local statistical models. The fusion approach takes advantage of learning from larger global data sets, but also exploits more specific spatial properties at local sites.
Resulting discoveries provide a better understanding of the aerosol data stream and allow developing more efficient and more accurate algorithms for retrieving geophysical parameters from raw data. Developed techniques apply to other Earth Observing System datasets (e.g. water and energy cycle; carbon cycle; weather and climate; or chemistry-climate connection) and also to other domains with complex spatio-temporal data properties.
Reported results are obtained in collaboration with A. Braverman (at JPL/Caltech), B. Han, K. Peng, S. Vučetić, L. Yong and Q. Xu (all at Temple University).

Petak, 2. septembar 2005. u 16h, sala 2, MI SANU:

Pierre Hansen, GERAD and HEC, University of Montreal, Canada
DISCRIMINANT ANALYSIS AND MATHEMATICAL PROGRAMMING

Abstract: The linear discriminant analysis problem, as expressed by Mangasarian, consists in finding a hyperplane which separates points of two given sets (good and bad ones) while minimizing the sum of distances, in Lp-Norm, of misclassified points to the hyperplane. We give a VNS heuristic valid for all p greater than or equal to 1, an improved exact algorithm for the case p=1 and new exact algorithms for the cases p=2 and p=infinity. We also discuss the choice of p, and the close objective of minimizing the number of misclassified points (sometimes called the L0-norm). (Joint work with Simon Blanchard, Gilles Caporossi and Alexandro Karam).

Četvrtak, 01. septembar 2005. u 12h, sala 61, ETF:

Dr. Zoran Obradović, Mathematical Institute SANU and Center for Information Science and Technology, Temple University, Philadelphia, PA
MICROARRAY FUNCTIONAL EXPRESSION PROFILES ANALYSIS TOOLBOX

Abstract: Microarray technology allows measuring expression level of thousands genes at once. Such data can in principle be used to identify genes that differentiate various groups of subjects. However, reducing uncertainty when analyzing such a high dimensional sample collected over a small number of subjects requires developing novel statistical techniques and also exploiting prior domain knowledge. In this talk we will present our novel software tool aimed at functional characterization of gene expression profiles. The tool consisting of profiles ranking and clustering modules is used to explore a hypothesis that genes with same or similar function are likely to have similar expression profiles. When analyzing 1,051 Gene Ontology (GO) terms represented by at least two genes in microarray data set of Plasmodium Falciparum (a parasite that causes malaria) Intraerythrocytic Developmental Cycle, we found that gene expression profiles in 550 of them are significantly (P<0.05) correlated. We represented each of the 550 significant GO terms with the functional expression profile defined as average expression profile of all genes annotated with a given GO term. Using Kmeans clustering, we clustered 199 profiles corresponding to GO molecular functions into 4 groups. This was repeated on 228 profiles corresponding to GO biological process. We quantified the clustering quality by introducing a measure of GO term similarity defined as the minimal distance between two GO terms in GO direct acyclic graph. The results based on this measure showed that the obtained clustering is biologically relevant which supports our hypothesis that genes with similar functions have similar expressions. Consistent findings were obtained when applying this fairly simple tool for microarray data analysis of Caccharomyces Cerevisiae, Mus Musculus and Home Sapiens cell cycle.
Results were obtained through a collaboration with Hongbo Xie, Slobodan Vučetić, Hao Sun and Pooja Hedge.

About speaker: Zoran Obradović is Director at the Center for Information Science and Technology, Associate Director at the Center for Quantitative Biology and Biomedical Mathematics and a Professor of Computer and Information Sciences at Temple University. His research interests focus on developing data mining and statistical learning technology for an efficient knowledge discovery at large databases. Funded by NSF, NIH, DOE and industry he contributed to about 160 refereed articles on these and related topics and to several academic and commercial software systems. For more details see www.ist.temple.edu/~zoran.

Ako zelite da se obavestenja o Vasim naucnim skupovima pojave u Newsletter of EMS (European Mathematical Society) i na Internetu na lokaciji EMS, onda se obratite na emsvesti@mi.sanu.ac.yu gde cete dobiti format obavestenja.