Ana Paula Tomás's Annual Report

Ana Paula Tomás's Annual Report

Year: 

2017

Brief description of the research activities: 

Research along the following lines:

(a) Guarding problems in rectlinear polygons:

(With Catarina Lobo Ferreira, BI grant, 2017) continued work on variants of the chromatic art gallery problem with edge-aligned vertex α-guards on orthogonal polygons (α-CAGP), for α=90°,180°,270°,360°, exploiting different mathematical models for the problem.  Some of these results were published in a conference (XVII Spanish Meeting on Computational Geometry, EGC 2017).

(b) Generation of rectilinear polygons:

(With Catarina Lobo Ferreira, BI grant, 2017) pursued work on a C++ library (http://genogons.dcc.fc.up.pt/index.html) for creating orthogonal polygons with a given number of vertices, and some subclasses (row-convex, column-convex, convex, path and spiral ogons). Its integration in CGAL (https://www.cgal.org/) is ongoing.

(c) Enumeration of row-and-column convex polyiamonds:

Continued the study carried out in 2016 (with G.Barequet) on enumeration of  "2-convex polyiamonds" (i.e., convex along two directions), along two lines: (1) a Temperley approach (slicing method) to obtain the generating functions for subclasses, as well as some recurrences suitable for a dynamic programming based method for computing exact counts; (2) approximate counts by exploiting their relation to polyominoes.

(d) Models and algorithms for variants of matching problems under preferences:

Revisited and extended previous work on a teacher recruitment problem (TRP),  motivated by ammendments to the teacher recruitment law in Portugal that led to significant delays in the assignment of teachers to schools in the Fall 2004 and 2014, causing a deep societal concern [Tomás,AP, SOFSEM 2018 https://doi.org/10.1007/978-3-319-73117-9_34] (accepted Sept 2017). This work shows that TRP is solvable in polynomial time if there is a single master list and that tie breaking rules that usually lead to unfair allocations can be discarded. On the other hand, if there are several master lists, the allocation problem is NP-hard if, for instance, we seek a stable matching of maximum size, which was somehow the reason for the problems raised in 2014.

Talks / Seminars / Courses : 

Speakers
Ana Paula Tomás

Computational applications: 

Catarina Lobo Ferreira, A.P.Tomás, "C++ library for creating orthogonal polygons" ( http://genogons.dcc.fc.up.pt/ )

Outreach activities: 

For secondary school students:
- ToPAS 2017 - Torneio de Programação para Alunos do Secundário (DCC-FCUP, May 2017), Scientific Committee Member (co-responsible for the problem set); http://www.dcc.fc.up.pt/ToPAS/

 

Reports: 

Reviewer for MathSciNet: MR3593911, MR3567620, MR3441165.

Error | CMUP

Error

The website encountered an unexpected error. Please try again later.