********************************** Title: Ant colony optimization for the variable sized bin packing problem Master Specialization: Algorithms and Programming Orientation: Research Thesis advisor(s): Dr. Christian Blum Ponent: not required Contact: cblum@lsi.upc.edu Student: open Thesis Description Ant colony optimization (ACO) is a swarm intelligence technique inspired by the shortest path finding capabilities of real ant colonies. When searching for food, ants initially explore the area surrounding their nest in a random manner. While moving, they leave a chemical pheromone trail on the ground. Ants can smell pheromone. When choosing their way, they tend to choose, in probability, paths marked by strong pheromone concentrations. As soon as an ant finds a food source, it carries some of the food back to the nest. During the return trip, the quantity of pheromone that an ant leaves on the ground may depend on the quantity and quality of the food. The pheromone trails will guide other ants to the food source. This indirect communication between the ants via pheromone trails---known as stigmergy---enables them to find shortest paths between their nest and food sources. The ACO metaheuristic uses this behaviour for solving combinatorial optimization problems. The aim of this thesis is to develop one ore more variants of the ACO metaheuristic to solve the variable sized bin packing problem (VSBPP), which is a combinatorial optimization problem. The VSBPP is a variant of the well-known one-dimensional bin packing problem. Comments for the Academic Comission None Requirements Programming in C++, some knowledge of heuristic methods, prior knowledge on ant colony optimization is not required Needed resources A computer with a C++ compiler. The cluster of the PCs of the ALBCOM research group will be available for the experimentation. ================================================== Title: A Library for Spatial and Metric Algorithms and Data Structures Master Specialization: Algorithmics and Programming Orientation: research Thesis advisor(s): Salvador Roura Contact: mercep@gmail.com, roura@lsi.upc.edu Student: Merc? Pons Crespo Thesis Description The purpose of this thesis is to develop and implement an efficient library of generic metric and spatial data structures and algorithms in the spirit of C++ Standard Template Library. The components of the library must be robust, flexible and must be throughly tested for performance tuning, providing ready-to-use solutions to common problems in the area, like nearest neighbor search or orthogonal range search, using state-of-the-art algorithms and data structures. Besides the implementation of the library itself, careful computational experiments must be conducted to establish the practical performance of its components, with systematic comparisons when the library provides alternative solutions to a given problem. The experiments should also serve to find variants and heuristics of the standard data structures and algorithms which improve the performance, e.g., simple criteria to order the exploration of a hierarchical index in a nearest neighbor search. This thesis could build upon the ideas laid down in the SMTL (Spatial and Metric Template Library), which was designed a few years ago by Guillem Marpons for his Final Project. Unfortunately, only a very small part of the SMTL was actually implemented, but it proposed a coherent and homogeneous framework for the kind of library that we want to develop for the present Master Thesis proposal. Requirements Very good programming skills, good knowledge of C++, a strong background in algorithms and data structures, good knowledge of statistical techniques and of analysis of algorithms. A good level for reading and writing in English is a must, and knowledge of LaTeX is also desirable. Needed resources Carrying out the computational experiments requires access to high performance computers. For the rest of the tasks, implementation, documentation, etc. a standard computer with access to Internet and common tools (editors, compilers, statistical and plotting packages, ...) should be enough. Access to the research literature and to the University library is also necessary. ========================================================= Title: The Hiring Problem: An Analytic and Experimental Study Master Specialization: Algorithmics and Programming Orientation: research Thesis advisor(s): Conrado Martínez Contact: conrado@lsi.upc.edu Student: Ahmed Helmi (ahelmi@lsi.upc.edu) Thesis Description The hiring problem is a simple model for on-line decision making under uncertainty. A company sequentially interviews candidates and for each one an irrevocable decision (hire or discard) must be taken based on the "quality" or score of the candidate and that of previous candidates, with no knowledge of the future. The problem is realted to the well known secretary problem and was very recently introduced by Broder et al. (SODA 2008). Archibald and Martínez (FPSAC 2009) have proposed an alternative model for the hiring problem which allows the use of combinatorial and analytic techniques to investigate this problem. In their work they have been able to prove several general theorems applying to large families of hiring strategies, and used them to derive very precise probabilistic analysis of a few particular important strategies. The thesis is a follow-up of the work of Archibald and Martínez, with two main concerns. On the one hand, the development of tools and programs (most likely in C++ and Matlab) that allows us to perform simulations of different hiring strategies and variations of the original hiring problem. These tools will be very useful to validate the theoretical models, but most importantly, for exploratory work. Part of the thesis will report the experimental work done with such tools. The other main concern will be the analytic research on this problem. Here, the goal is to provide general results for some new parameters and analyze their behavior in particular important strategies: - Time of the last hiring - Distance between the two last hirings - Score the best candidate not hired Another part will be devoted to the analysis of a variant of the problem where it is possible to fire candidates. In particular, one goal is to analyze an important family of strategies called "replacement strategies"; these achieve optimal quality at the expense of firing candidates. Hence, a parameter of upmost importance for these strategies is the number of firings, which will be analyzed in the thesis. Other possible extensions include the analysis of multicriteria hiring, when there are k concepts and each candidate has k scores, one for each concept. Comments for the Academic Comission Requirements - Good mathematical skills, specially in combinatorics, discrete mathematics and probability. - Good background in algorithmics - Good knowledge of programming, proficiency in C++ and/or other programming languages and some computer algebra system (e.g., Maple, Matlab, Mathematica); knowldege of Unix/Linux operating system Needed resources - A computer to do the programming, experiments, computations, etc. with all the necessary software (which is either free or the UPC has already licenses) - Access to Internet and to bibliographic resources - Access to the LCLSI resources and services (printers, scanner, disks, ...) ===========================================================