Pizzas<\/strong><\/td>\n| <\/td>\n | <\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n <\/p>\n Student talks\u00a0<\/strong><\/p>\nMonday 17:45-18:05 Felipe Benitez
\nTuesday 17:45-18:05 Viviana M\u00e1rquez
\nTuesday 18:05-18:25 Raimundo Saona
\nWednesday 17:45-18:05 Bruno Che Le\u00f3n
\nThursday 17:45-18:05 Fabricio Mendoza
\nThursday 18:05-18:20 (TBD)<\/p>\n Felipe Benitez<\/strong>:\u00a0 Signed Graph Embedding on the Circumference
\nA signed graph is a mathematical structure composed by a graph G = (V,E) and a sign assignment on\u00a0its edges s : E \u2192 {+1,\u22121}. Signed graphs are useful to represent binary relation models, these are model\u00a0in which the relationship between two entities can be described as a positive or a negative relation, for\u00a0example friendship and enmity, or any kind of two-type relation where both relations are opposite to each\u00a0other. An example of its usefulness is a social network represented by signed graphs where positive edges\u00a0represent friendship between two people and negative edges represent enmity between two people. A natural\u00a0assumption on social behavior is that everyone wants to be closer to their friend than their enemies. We\u00a0will call this assumption the closeness condition Our work represent that idea and it is defined as a sign a\u00a0graph embedded on a metric space where every vertex is closer to its positives relations than its negative
\nrelations. That is, a signed graph embedding under the closeness condition.
\nThere has been studies on this problem where they respond an easier question: Which signed graphs\u00a0can be embedded on R under the closeness condition? In [1] it is shown that decide when a given graph\u00a0can be embedded or not on R under the closeness condition is an NP-complete problem. Moreover, in [2]\u00a0they give a characterization for all the complete signed graphs (i.e. complete graphs with signs) that can be\u00a0embedded on R under the closeness condition. Even more, they give an algorithm to find such embedding.
\nOn my thesis work [3] we move along this way further more. This time considering the metric space to\u00a0be the circumference C, in which the distance between two points in C is given by the smallest arc length\u00a0defined by those points:
\ndC(p1,p2) = m\u00edn{|\u03c01 \u2212\u03c02|,2\u03c0 \u2212|\u03c01 \u2212\u03c02|},
\nwhere \u03c01 y \u03c02 are the angles defined by p1 and p2 respectively and measured in radians.
\nTherefore, the main problem is: Given a signed graph G = (V,E+\u00a0\u222a E\u2212), Can G = (V,E+\u222a E\u2212) be
\nembedded on C under the closeness condition? The results of this work summarize in:
\n\u00a0
\nA1: We found a characterization for complete signed graphs for which exists such embedding on C and we\u00a0give and algorithm to find such embedding.
\nA2: We give forbidden graphs pattern to the main problem. This patterns did not require the graph to be\u00a0complete.<\/p>\n[1] Marek Cygan, Marcin Pilipczuk, Micha\u0142 Pilipczuk, and Jakub Onufry Wojtaszczyk. Sitting closer to friends than enemies, revisited. Theory of computing systems, 56(2):394\u2013405, 2015.
\n[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\u2013399, 2011.
\n[3] Felipe Ben\u00edtez Ulloa. Incrustaci\u00f3n de Grafos con Signos en la Circunferencia. https:\/\/www.icm.udec. cl\/userfiles\/file\/tesis\/TesisFelipeBenitez.pdf. Tesis de grado, Universidad de Concepci\u00f3n, 2017. <\/p>\nFabricio Mendoza<\/strong>:\u00a0Distributed Spectral Clustering
\nClustering 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
\nof the data to and out an optimal partition and then use clustering in a distributed setting.
\nTo 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.<\/p>\n[1] CHEN, Jiecao, et al. Communication-optimal distributed clustering. En Advances in Neural Information Processing Systems. 2016. p. 3727-3735.<\/p>\nViviana M\u00e1rquez<\/strong>:\u00a0 Compositions of n<\/em> with parts less or equal to k<\/em><\/p>\nLet n<\/em> be a positive integer. A composition of n<\/em> is an organized tuple of positive integers that adds to n<\/em>. For example, all possible compositions of 3 are (1,1,1),(2,1),(1,2),(3). Let C_n^{(k)}<\/em> be the number of compositions of n<\/em> that involves numbers less or equal to k<\/em>. In this work, we will show a non-recursive formula to find C_n^{(k)}<\/em>\u00a0when n<= 2k+1<\/em>, which is more efficient than the one previously known.<\/p>\nRaimundo Saona<\/strong>: Prophet inequality, an overview in optimal stopping theory.<\/p>\nThis 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.<\/p>\n Bruno Che Le\u00f3n<\/strong>: An Approximation Algorithm applied to Job Shop<\/p>\nThe Job Shop Schedulng Problem is one of the most classic problems
\nof combinatorial optimization. In this work, we propose an approximation
\nalgorithm that uses an integer formulation indexed in increasing time intervals
\nand the alpha-point technique. The performance of the algorithm is analyzed
\nthrough simulations and instances of the OR-Library, obtaining solutions in a
\nshort time and values relatively close to the optimum value.<\/p>\n","protected":false},"excerpt":{"rendered":" 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 … Contin\u00fae leyendo Programa<\/span> →<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"parent":0,"menu_order":2,"comment_status":"closed","ping_status":"closed","template":"","meta":{"inline_featured_image":false,"footnotes":""},"class_list":["post-12","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/eventos.cmm.uchile.cl\/discretas2018\/wp-json\/wp\/v2\/pages\/12","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/eventos.cmm.uchile.cl\/discretas2018\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/eventos.cmm.uchile.cl\/discretas2018\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/eventos.cmm.uchile.cl\/discretas2018\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/eventos.cmm.uchile.cl\/discretas2018\/wp-json\/wp\/v2\/comments?post=12"}],"version-history":[{"count":10,"href":"https:\/\/eventos.cmm.uchile.cl\/discretas2018\/wp-json\/wp\/v2\/pages\/12\/revisions"}],"predecessor-version":[{"id":156,"href":"https:\/\/eventos.cmm.uchile.cl\/discretas2018\/wp-json\/wp\/v2\/pages\/12\/revisions\/156"}],"wp:attachment":[{"href":"https:\/\/eventos.cmm.uchile.cl\/discretas2018\/wp-json\/wp\/v2\/media?parent=12"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}} |