###### Home / Seminars

## Seminars

If you are interested to collaborate or to give a talk, please contact Prof. Rafael Crivellari Saliba Schouery, currently responsible for seminars series. All are very welcome!

### Upcoming seminar(s)

##
**16/12/2022 10:00, room 85.**

**“Latin Squares. Complexity and Approximability”**

**VĂtor Gomes Chagas**

A latin square is an n x n grid filled with n elements in such a way that no element occurs more than once in any row or column of the grid. The concept of latin squares was first mathematically defined and studied by Euler in the 17th century, and since then algebraic and combinatorial properties have been extensively investigated. Regarding the structure of latin squares, some natural questions may arise. Given a latin square with some cells left empty, is it possible to complete it? In negative case, how many cells can be filled without violating the latin square constraints? These questions refer respectively to the decidability of latin squares completion and the approximability of latin squares extension, We present some known results concerning these questions from a computational point of view. We show that deciding if a parital latin square is completable is NP-complete, and with respect to the approximability of latin squares extension, we present some approximation algorithms for the problem, namely a greedy algorithm, some matching based algorithms and a local search approach.

You can subscribe to LOCO seminars by adding the following URL to your calendar:

https://www.loco.ic.unicamp.br/seminars/locoseminars.ics (add to Google Calendar, iCal)