Monday | Tuesday | Wednesday | Thursday | Friday | |
8:30-9:00 | Registration | ||||
9:00-10:15 | Oshman | Haxell | Mehlhorn | Oshman | Haxell |
10:15-10:30 | Coffee break | Coffee break | Coffee break | Coffee break | Coffee break |
10:30-11:45 | Trabajo | Trabajo | Trabajo | Trabajo | Mehlhorn |
11:45-13:00 | Haxell | Mehlhorn | Oshman | Haxell | Oshman |
13:00-15:00 | Lunch | Lunch | Lunch | Lunch | BBQ |
15:00-16:15 | Mehlhorn | Oshman | Haxell | Mehlhorn | |
16:15-16:30 | Coffee break | Coffee break | Coffee break | Coffee break | |
16:30-17:45 | Trabajo | Trabajo | Trabajo | Trabajo | |
17:45-18:00 | Talk | Talk | Talk | Talk | |
18:00-18:15 | Cheese & Wine | Talk | Pizzas | Talk | |
18:15-19:15 | Cheese & Wine | Pizzas |
Student talks
Monday 17:45-18:05 Felipe Benitez
Tuesday 17:45-18:05 Viviana Márquez
Tuesday 18:05-18:25 Raimundo Saona
Wednesday 17:45-18:05 Bruno Che León
Thursday 17:45-18:05 Fabricio Mendoza
Thursday 18:05-18:20 (TBD)
Felipe Benitez: Signed Graph Embedding on the Circumference
A signed graph is a mathematical structure composed by a graph G = (V,E) and a sign assignment on its edges s : E → {+1,−1}. Signed graphs are useful to represent binary relation models, these are model in which the relationship between two entities can be described as a positive or a negative relation, for example friendship and enmity, or any kind of two-type relation where both relations are opposite to each other. An example of its usefulness is a social network represented by signed graphs where positive edges represent friendship between two people and negative edges represent enmity between two people. A natural assumption on social behavior is that everyone wants to be closer to their friend than their enemies. We will call this assumption the closeness condition Our work represent that idea and it is defined as a sign a graph embedded on a metric space where every vertex is closer to its positives relations than its negative
relations. That is, a signed graph embedding under the closeness condition.
There has been studies on this problem where they respond an easier question: Which signed graphs can be embedded on R under the closeness condition? In [1] it is shown that decide when a given graph can be embedded or not on R under the closeness condition is an NP-complete problem. Moreover, in [2] they give a characterization for all the complete signed graphs (i.e. complete graphs with signs) that can be embedded on R under the closeness condition. Even more, they give an algorithm to find such embedding.
On my thesis work [3] we move along this way further more. This time considering the metric space to be the circumference C, in which the distance between two points in C is given by the smallest arc length defined by those points:
dC(p1,p2) = mín{|π1 −π2|,2π −|π1 −π2|},
where π1 y π2 are the angles defined by p1 and p2 respectively and measured in radians.
Therefore, the main problem is: Given a signed graph G = (V,E+ ∪ E−), Can G = (V,E+∪ E−) be
embedded on C under the closeness condition? The results of this work summarize in:
A1: We found a characterization for complete signed graphs for which exists such embedding on C and we give and algorithm to find such embedding.
A2: We give forbidden graphs pattern to the main problem. This patterns did not require the graph to be complete.
[2] A.-M. Kermarrec and C. Thraves. Can everybody sit closer to their friends than their enemies? In Proceedings of the 36th International Symposium on Mathematical Foundations of Computer Science (MFCS), pages 388–399, 2011.
[3] Felipe Benítez Ulloa. Incrustación de Grafos con Signos en la Circunferencia. https://www.icm.udec. cl/userfiles/file/tesis/TesisFelipeBenitez.pdf. Tesis de grado, Universidad de Concepción, 2017.
Fabricio Mendoza: Distributed Spectral Clustering
Clustering is an important tool in big data. Its purpose is to partition in clusters a given set of points in a d-dimensional space, where the partition is optimal, that is, every subset must has a balanced number of points and they must be similar among them. A typical approach for finding out clusters is to choose k random points and verify which points are similar. If two points are very similar, then they belong to the same cluster. In this talk, we will discuss distributed spectral clustering, which uses algebraic properties
of the data to and out an optimal partition and then use clustering in a distributed setting.
To accomplish this the data is represented as a graph, where every point is a vertex and there exist an edge between two vertices if they are similar. The concept of similarity is not unique and in this case is given by a function called similarity function. In real world applications the data is not always in the same place, and therefore, clustering on distributed data can be very expensive in terms of communication. A protocol was designed to accomplish this in the coordinator model, where many datacenters or servers are connected to a single server or central datacenter. Every datacenter computes a reduced version of its data and sends it to the central datacenter. Then, the central datacenter executes the spectral clustering and send back the results (clusters) to every datacenter.
Viviana Márquez: Compositions of n with parts less or equal to k
Let n be a positive integer. A composition of n is an organized tuple of positive integers that adds to n. For example, all possible compositions of 3 are (1,1,1),(2,1),(1,2),(3). Let C_n^{(k)} be the number of compositions of n that involves numbers less or equal to k. In this work, we will show a non-recursive formula to find C_n^{(k)} when n<= 2k+1, which is more efficient than the one previously known.
Raimundo Saona: Prophet inequality, an overview in optimal stopping theory.
This talk surveys the origin and development of what has come to be known as “prophet inequality” in optimal stopping theory, which is concerned with the problem faced by a seller, with imperfect information, who has a single object to sell to one of several possible buyers. I’ll present some of the principal variants of the problem and desired characteristics of a solution mechanism. Then, some well known results and finish presenting a simple proof of one of them.
Bruno Che León: An Approximation Algorithm applied to Job Shop
The Job Shop Schedulng Problem is one of the most classic problems
of combinatorial optimization. In this work, we propose an approximation
algorithm that uses an integer formulation indexed in increasing time intervals
and the alpha-point technique. The performance of the algorithm is analyzed
through simulations and instances of the OR-Library, obtaining solutions in a
short time and values relatively close to the optimum value.