Titulo Estágio
Engineering Algorithms for Finding the Maxima of a Point Set
Área Tecnológica
Sistemas Evol. e Comp.
Local do Estágio
ECOS/CISUC
Enquadramento
For a given set of points S, the maxima finding problem consists on finding the subset of these points for which there is no other point in S that has larger or equal coordinates. This problem arises in pratical applications, such as in multicriteria optimization. Many algorithms were already proposed in the literature, based on dimensional sweep, divide-and-conquer and quadtrees. However, there is no comprehensive study on the effectiveness of these approaches in practice, as well as extensions to different computational models.
Objetivo
The goal is to perform an in-depth computational study of maxima finding algorithms described in the literature for an arbitrary number of dimensions. Some of these algorithms are described in “Mikkel T. Jensen: Reducing the run-time complexity of multiobjective EAs: The NSGA-II and other algorithms. IEEE Trans. Evolutionary Computation, 7(5): 503-515 (2003).“ Also, the student will explore the application of these algorithms under different computational models, such as on-line (points are given over time), external memory (need to use external memory in order to process large number of points), cache-oblivious (use of different levels of cache) and resilient (correctedness under memory failures) models.
Plano de Trabalhos - Semestre 1
1 Month: Problem identification
2 Months: Literature review on computational geometry and computational models (on-line, external memory, cache-oblivious and resilient algorithms)
1 Month: Writing of the preliminary report (includes a description of the
algorithms for maxima finding)
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 are highly preferable. Good experience in C,
C++, or Java is also necessary.
Orientador
Luis Paquete
paquete@dei.uc.pt 📩