Titulo Estágio
Algorithms for the multiobjective minimum spanning tree problem
Área Tecnológica
Sistemas Evol. e Comp.
Local do Estágio
CISUC/ECOS
Enquadramento
Multiobjective Minimum Spanning Tree Problems arise in many real-life problems, for instance, when planning a telecommunication network that minimizes the length of the cable and maximizes the network reliability. Clearly, there is no single optimal spanning tree for this problem; for instance, the most reliable network may not be the one that uses less cable. Hence, for this problem, one has to develop algorithms whose outcome is a set of “trade-off” spanning trees, and from which the user chooses the one he/she prefers the most. This raises several challenging algorithmic issues.
Objetivo
The student will develop algorithms for the Multiobjective Minimum Spanning tree, by following the descriptions available in the literature, such as extensions of Kruskal and Prim’s algorithms. He/she will perform a large experimental analysis by taking into account several types of instances. In a second phase, he/she will develop an exploratory analysis on the the structure of the solutions for the this problem. In particular, the aim is to know whether those solutions are “close” to each other or not; for instance, for the case of Minimum Spanning Tree Problem, we say that two trade-off solutions are close if they differ only with respect to a small number of edges. To know whether this is true for all solutions is highly relevant, since we could use this information to develop very efficient algorithms. (see similar study for shortest path problem in L. Paquete, J.L. Santos, D.J. Vaz, Efficient paths by local search, Proc. Of VII ALIO/EURO, Workshop on Applied Combinatorial Optimization, available at http://eden.dei.uc.pt/~paquete/papers/alio2011.pdf)
Plano de Trabalhos - Semestre 1
1 Month: Problem identification
2 Months: Literature review on multiobjective optimization and minimum spanning tree
1 Month: Writing of the preliminary report (includes a description of the problem to be tackled and possible solution approaches).
Plano de Trabalhos - Semestre 2
2 Months: Algorithm implementation
1 Month: Experimental analysis
1 Month: Thesis writing.
Condições
The ECOSLab and its computing resources are available for performing experiments. The research group owns a computer cluster for the
experimental analysis.
Observações
The student will work in a very motivated research group with wide international visibility. He/she will strengthen his abilities on the design and analysis of algorithms and data structures for problem solving and will develop advanced programming skills. This type of work is appropriate to students that want to follow an academic career in design and analysis of algorithms.
Students with excellent record on Algorithms and Data Structures, Advanced Programming Lab and Evolutionary Computation are highly preferable. Good experience in C, C++, or Java is also necessary.
Orientador
Luis Paquete
paquete@dei.uc.pt 📩