An Experimental Comparison of Distributed Algorithms Simulating Human Detailers and an Extension of the Kuhn-Munkres Algorithm for the Sailor Assignment Problem (Sap).

FACULTAD DE INGENIERIA

UNIDAD DE POSGRADOS

THESIS PROPOSAL

MASTER'S THESIS

1. PROPONENT: Jesús Alfredo Burbano Portilla

ID: 2 299699

2. PROGRAM: Maestría en Ingeniería-Ingeniería de Sistemas y Computación

3. PROPOSED DIRECTOR: Germán Hernández, PhD

DEPARTMENT: Ingeniería de Sistemas

CO-DIRECTOR: Dipankar Dasgupta, PhD

4. TITLE: An experimental comparison of distributed algorithms simulating human detailers and an extension

of the Kuhn-Munkres algorithm for the Sailor Assignment Problem (SAP).

AREA: Experimental analysis of algorithms, Matching, Distribute and Randomized Algorithms

LINE OF RESEARCH: Computer Sciences

5. BACKGROUND AND JUSTIFICATION: Matching problems, also known as assignment and correspondence

problems, are one of the fundamental classes of problems in computer science. In a matching

problem we are given n (agents, boys, sailors, bets, ...) to be match with m (tasks, girls, jobs,

adwords, ...), we may have restrictions on the agents can perform the particular tasks and also we

may have preference lists or a cost of assigning an agent to a task, or both; and the problem is how

to pair, match, assign, make them correspond o, respecting the constrains and with an optimal

cost. In a wide range of practical situations we nd many examples of matching problems with thousands

of elements to match [Abdulkadiroglu and Roth, 2005, Abraham et al., 2007, Garrett et al., 2005,

Manlove et al., 2007, Teo et al., 2001]. The two basic models are one-to-one and many-to-one matching

models. If one agent is matched with only one task on the other side, then this is a one-to-one

matching [Gale and Shapley, 1962]. But if one agent is matched with more than one task on the other

side, such as clustering data sets, assigning students to schools, etc., then is a many-to-one matching

[Baiou and Balinski, 2000, Roth and Rothblum, 1993]. Matching may require to accomplish some

conditions to improve some outcomes (to guarantee stability,...