{"id":10,"date":"2018-05-17T21:14:19","date_gmt":"2018-05-17T21:14:19","guid":{"rendered":"http:\/\/eventos.cmm.uchile.cl\/discretas2019\/?page_id=10"},"modified":"2019-01-07T20:57:23","modified_gmt":"2019-01-07T20:57:23","slug":"programa","status":"publish","type":"page","link":"https:\/\/eventos.cmm.uchile.cl\/discretas2019\/programa\/","title":{"rendered":"Programa"},"content":{"rendered":"\n\n\n\n\n\n\n\n\n\n\n\n\n\n
<\/td>\nLunes<\/strong>
\nChair: <\/span>
\n Verschae<\/span><\/td>\n		Martes<\/strong>
\nChair: <\/span>
\n Matamala<\/span><\/td>\n		Mi\u00e9rcoles<\/strong>
\nChair: <\/span>
\n Rapaport<\/span><\/td>\n		Jueves<\/strong>
\nChair: <\/span>
\n Montealegre<\/span><\/td>\n		Viernes<\/strong>
\nChair: <\/span>
\n Soto<\/span><\/td>\n<\/tr>\n
8:30 – 9:00<\/td>\nInscripci\u00f3n<\/strong><\/td>\nTareas<\/strong><\/td>\nTareas<\/strong><\/td>\nTareas<\/strong><\/td>\nTareas<\/strong><\/td>\n<\/tr>\n
9:00 – 10:15<\/td>\nBubeck<\/strong><\/td>\nBubeck<\/strong><\/td>\nPapadimitriou<\/strong><\/td>\nPapadimitriou<\/strong><\/td>\nPapadimitriou<\/strong><\/td>\n<\/tr>\n
\u00a010:15 – 10:30<\/td>\nCoffee break<\/strong><\/td>\nCoffee break<\/strong><\/td>\nCoffee break<\/strong><\/td>\nCoffee break<\/strong><\/td>\nCoffee break<\/strong><\/td>\n<\/tr>\n
10:30 – 11:45<\/td>\nTrabajo<\/strong><\/td>\nTrabajo<\/strong><\/td>\nTrabajo<\/strong><\/td>\nTrabajo<\/strong><\/td>\nTrabajo<\/strong><\/td>\n<\/tr>\n
11:45 – 13:00<\/td>\nFomin<\/strong><\/td>\nFomin<\/strong><\/td>\nBubeck<\/strong><\/td>\nFomin<\/strong><\/td>\nFomin<\/strong><\/td>\n<\/tr>\n
13:00 – 15:00<\/td>\n\u00a0Almuerzo<\/strong><\/td>\n\u00a0Almuerzo<\/strong><\/td>\n\u00a0Almuerzo<\/strong><\/td>\n\u00a0Almuerzo<\/strong><\/td>\nActividad<\/strong><\/td>\n<\/tr>\n
15:00 – 16:15<\/td>\n\u00a0Bubeck<\/strong><\/td>\nBubeck<\/strong><\/td>\nPapadimitriou<\/strong><\/td>\nPapadimitriou<\/strong><\/td>\n<\/td>\n<\/tr>\n
16:15 – 16:30<\/td>\nCoffee break<\/strong><\/td>\nCoffee break<\/strong><\/td>\nCoffee break<\/strong><\/td>\nCoffee break<\/strong><\/td>\n<\/td>\n<\/tr>\n
16:30 – 17:45<\/td>\nFomin<\/strong><\/td>\nTrabajo<\/strong><\/td>\nTrabajo<\/strong><\/td>\nTrabajo<\/strong><\/td>\n<\/td>\n<\/tr>\n
17:45 – 19:00<\/td>\nTrabajo<\/strong><\/td>\nCharla<\/strong><\/td>\n\u00a0Charla<\/strong><\/td>\n\u00a0Charla<\/strong><\/td>\n<\/td>\n<\/tr>\n
19:00 – 21:00<\/td>\n\u00a0Actividad<\/strong><\/td>\n<\/td>\n\u00a0<\/strong><\/td>\n<\/td>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

Student talks:<\/strong><\/p>\n

Tuesday:<\/strong>
\n17:50 – 18:25 Lukas Noelke,
\n18:25 – 19:00 Andr\u00e9s Cristi.<\/p>\n

Wednesday:<\/strong>
\n17:45 – 18:20 Wanchote Jiamjitrak,
\n18:25 – 19:00 Javier T.\u00a0 Akagi.<\/p>\n

Jueves: <\/strong>
\n17:45 – 18:20 Carolina Gonz\u00e1lez,
\n18:25 – 19:00 Arturo Merino.<\/p>\n

Lukas Noelke<\/strong>
\nTitle:<\/strong> Packing Anchored Rectangles
\nAbstract:<\/strong> Let \\( P=\\{p_1,\\ldots,p_n\\}\u00a0\\) be a set of points in the unit square and \\((\\alpha,\\beta) \\in [0,1]^2\\). An \\((\\alpha,\\beta)\\)-anchored rectangle packing is a set \\(\\mathcal{R}=\\{R_1,\\ldots,R_n\\}\\) of disjoint, axis-aligned rectangles. We require, that for each rectangle\u00a0\\(R_i=(a,a+x)\\times(b,b+y) \\subseteq [0,1]^2\\) it holds that \\(p_i = (a+\\alpha x, b+\\beta y)\\). Aditionally,\u00a0\\(R_i\\) may not contain any point in \\(P \\setminus\\{p_i\\}\\). In the $(\\alpha,\\beta)[\/latex]-anchored rectangle packing problem, we look for a packing that maximizes the area covered by the rectangles. The special case with \\((\\alpha,\\beta)=(0,0)\\) and \\((0,0)\\in P\\) corresponds to the well-known lower-left anchored rectangle packing (LLARP). For the LLARP problem, we consider two types of resource augmentation. In the first, we allow each point in \\(P\\) to be moved by a small amount \\(\\varepsilon>0\\) within the unit square. For this setting, we give a polynomial time algorithm that finds a set of rectangles that covers at least as much area as the optimal solution to the original problem. In the second, we allow each pair of rectangles to overlap by a strip whose shortest side length is at most \\(\\varepsilon>0\\). Here, we give a polynomial time algorithm that finds a set of rectangles that covers at least a \\((1-\\varepsilon)\\)-fraction of the optimum of the original problem. For the center-anchored rectangle packing (CARP), where \\((\\alpha,\\beta)=(\\frac{1}{2},\\frac{1}{2})\\), we give a PTAS that extends to all \\((\\alpha,\\beta) \\in (0,1)^2\\). We also show that the CARP problem is NP-hard.<\/p>\n

This is joint work with Antonios Antoniadis, Andr\u00e9s Cristi, Felix Biermeier, Christoph Damerius, Ruben Hoeksma, Dominik Kaaser, and Peter Kling.<\/p>\n

Andres Cristi<\/strong>
\nTitle<\/strong>: Negative Prices in Network Pricing Games
\nAbstract:<\/strong> A Stackelberg network pricing game is a two-stage game, in which, in the first stage, a leader sets prices for a given subset of edges so as to maximize profit (all other edges have a fixed cost), and, in the second stage, one or multiple followers choose a shortest path from their source to their sink. Counterintuitively, the usage of negative prices by the leader may in fact increase his profit. In this talk I will deal with the following two questions. First, for which network topologies can the leader increase profit by using negative prices? Second, how much extra profit can the leader obtain by setting negative prices? I will prove that only series-parallel graphs are immune to this paradox, and that the profit achievable with negative prices can be a factor\u00a0\\(\\Theta(\\log n)\\) larger than the maximum profit with non-negative prices, where n is the number of nodes in the graph. If time permits, I will also talk about how allowing negative prices relates to allowing bundling strategies in general.<\/p>\n

This is joint work with Marc Schr\u00f6der<\/p>\n

Wanchote Jiamjitrak<\/strong>
\nTitle:<\/strong> Illustrative charging scheme for BST
\nAbstract:<\/strong> A 30-year-old famous dynamic optimality conjecture states that “For any sufficiently long search sequence, the cost of splay tree is at most any dynamic binary search tree (BST)”. In this talk, we will show the geometric view of BST algorithm. Along with our charging scheme, we simplify the known result that splay tree is static optimal, i.e., “For any sufficiently long search sequence, the cost of splay tree is at most any static BST”.<\/p>\n

Javier T. Akagi<\/strong>
\nTitle:<\/strong> Hard and Easy Instances of L-Tromino Tilings
\nAbstract:<\/strong> In this work we study tilings of regions in the square lattice with L-shaped trominoes. Deciding the existence of a tiling with L-trominoes for an arbitrary region in general is NP-complete, nonetheless, we identify restrictions to the problem where it either remains NP-complete or has a polynomial time algorithm. First, we characterize the possibility of when an Aztec rectangle has an L-tromino tiling, and hence also an Aztec diamond; if an Aztec rectangle has an unknown number of defects or holes, however, the problem of deciding a tiling is NP-complete.\u00a0 <\/span>Then, we study tilings of arbitrary regions where only \\(180^\\circ\\) rotations of L-trominoes are available. For this particular case we show that deciding the existence of a tiling remains NP-complete; yet, if a region does not contains certain so-called\u00a0 “forbidden polyominoes” as subregions, then there exists a polynomial time algorithm for deciding a tiling.<\/p>\n

Carolina Gonz\u00e1lez<\/strong>
\nTitle:<\/strong> Grundy domination number in block graphs
\nAbstract:<\/strong> A sequence \\(S = (v_1, \\ldots, v_k)\\) of vertices of a graph \\(G\\) is called dominating<\/em> if\u00a0\\(\\{v_1, \\ldots, v_k\\}\\) is a dominating set in\u00a0\\(G\\), and it is called legal<\/em> if each vertex of \\(S\\) dominates at least one vertex that is not dominated by its preceding vertices in the sequence. The maximum length of a legal dominating sequence in \\(G\\) is the Grundy domination number<\/em>\u00a0of\u00a0\\(G\\).
\nBre\u0161ar et al.[1] proved that the problem of determining the Grundy domination number is NP-complete, even for chordal graphs. They also show efficient algorithms for trees and other classes of graphs.<\/p>\n

In this talk we present a linear time algorithm that computes the Grundy domination number for block graphs. This result originally appeared in [2].<\/p>\n[1] B. Bre\u0161ar, T. Gologranc, M. Milani\u010d, D. F. Rall, R. Rizzi. Dominating sequences in graphs. Discrete Mathematics, 336:22-36, 2014.
\n[2] C. L. Gonz\u00e1lez. El problema de dominaci\u00f3n Grundy en grafos block y grafos ara\u00f1a bien etiquetada. Undergraduate thesis, Universidad Nacional de Rosario, 2017.<\/p>\n

 <\/p>\n

Arturo Merino<\/strong>
\nTitulo:<\/strong> Regla azul y roja para MST con incertidumbre.
\nAbstract:<\/strong> Nos interesamos en el problema de\u00a0 \u00e1rbol generador de peso m\u00ednimo (MST) en un contexto donde los pesos son inciertos. Inicialmente, para cada arista e de un grafo \\((V, E)\\) se conocer \u00e1 un conjunto no vac\u00edo \\(A_e\\subseteq \\mathbb{R}\\) que contiene los posibles pesos de la arista e. Eventualmente los \u201cverdaderos pesos\u201d son revelados, obteniendo un \\(w_e \\in A_e\\) para cada arista \\(e\\). Diremos que un\u00a0 \u00e1rbol es uniformemente m\u00ednimo si es de peso m\u00ednimo sin importar cuales sean los verdaderos pesos. El problema de MST uniforme consiste en encontrar un\u00a0 \u00e1rbol uniformemente m\u00ednimo o determinar que ninguno existe. Mediante t\u00e9cnicas de minmax regret se sabe que este problema puede ser resuelto en tiempo polinomial si cada \\(A_e\\) es un intervalo cerrado y acotado.
\nPor otro lado, la regla azul y roja han jugado un rol fundamental en el desarrollo de algoritmos eficientes para el problema de MST sin incertidumbre, proveen una interesante visi\u00f3n estructural y son el motor detr\u00e1s de los algoritmos de Prim, Kruskal y Boruvka.
\nEn esta charla exploraremos una generalizaci\u00f3n de la regla azul y roja para el caso donde los pesos son inciertos. Aprovech\u00e1ndonos de estas nuevas ideas estructurales daremos una caracterizaci\u00f3n de la existencia de \u00e1rboles uniformemente m\u00ednimos y mostraremos un nuevo algoritmo a tiempo polinomial para el problema de MST uniforme (sin restricci\u00f3n alguna sobre los\u00a0\\(A_e\\)). Por\u00a0 \u00faltimo, hablaremos de problemas relacionados que aparecen al considerar incertidumbre en los pesos.<\/p>\n","protected":false},"excerpt":{"rendered":"

Lunes Chair: Verschae Martes Chair: Matamala Mi\u00e9rcoles Chair: Rapaport Jueves Chair: Montealegre Viernes Chair: Soto 8:30 – 9:00 Inscripci\u00f3n Tareas Tareas Tareas Tareas 9:00 – 10:15 Bubeck Bubeck Papadimitriou Papadimitriou Papadimitriou \u00a010:15 – 10:30 Coffee break Coffee break Coffee break Coffee break Coffee break 10:30 – 11:45 Trabajo Trabajo Trabajo Trabajo Trabajo 11:45 – 13:00 … Contin\u00fae leyendo Programa<\/span> →<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"parent":0,"menu_order":4,"comment_status":"closed","ping_status":"closed","template":"","meta":{"inline_featured_image":false,"footnotes":""},"class_list":["post-10","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/eventos.cmm.uchile.cl\/discretas2019\/wp-json\/wp\/v2\/pages\/10","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/eventos.cmm.uchile.cl\/discretas2019\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/eventos.cmm.uchile.cl\/discretas2019\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/eventos.cmm.uchile.cl\/discretas2019\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/eventos.cmm.uchile.cl\/discretas2019\/wp-json\/wp\/v2\/comments?post=10"}],"version-history":[{"count":64,"href":"https:\/\/eventos.cmm.uchile.cl\/discretas2019\/wp-json\/wp\/v2\/pages\/10\/revisions"}],"predecessor-version":[{"id":209,"href":"https:\/\/eventos.cmm.uchile.cl\/discretas2019\/wp-json\/wp\/v2\/pages\/10\/revisions\/209"}],"wp:attachment":[{"href":"https:\/\/eventos.cmm.uchile.cl\/discretas2019\/wp-json\/wp\/v2\/media?parent=10"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}