Programa

Lunes
Chair:
Verschae
Martes
Chair:
Matamala
Miércoles
Chair:
Rapaport
Jueves
Chair:
Montealegre
Viernes
Chair:
Soto
8:30 – 9:00 Inscripción Tareas Tareas Tareas Tareas
9:00 – 10:15 Bubeck Bubeck Papadimitriou Papadimitriou Papadimitriou
 10: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 Fomin Fomin Bubeck Fomin Fomin
13:00 – 15:00  Almuerzo  Almuerzo  Almuerzo  Almuerzo Actividad
15:00 – 16:15  Bubeck Bubeck Papadimitriou Papadimitriou
16:15 – 16:30 Coffee break Coffee break Coffee break Coffee break
16:30 – 17:45 Fomin Trabajo Trabajo Trabajo
17:45 – 19:00 Trabajo Charla  Charla  Charla
19:00 – 21:00  Actividad  

Student talks:

Tuesday:
17:50 – 18:25 Lukas Noelke,
18:25 – 19:00 Andrés Cristi.

Wednesday:
17:45 – 18:20 Wanchote Jiamjitrak,
18:25 – 19:00 Javier T.  Akagi.

Jueves:
17:45 – 18:20 Carolina González,
18:25 – 19:00 Arturo Merino.

Lukas Noelke
Title: Packing Anchored Rectangles
Abstract: Let \( P=\{p_1,\ldots,p_n\} \) 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 \(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, \(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.

This is joint work with Antonios Antoniadis, Andrés Cristi, Felix Biermeier, Christoph Damerius, Ruben Hoeksma, Dominik Kaaser, and Peter Kling.

Andres Cristi
Title: Negative Prices in Network Pricing Games
Abstract: 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 \(\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.

This is joint work with Marc Schröder

Wanchote Jiamjitrak
Title: Illustrative charging scheme for BST
Abstract: 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”.

Javier T. Akagi
Title: Hard and Easy Instances of L-Tromino Tilings
Abstract: 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.  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  “forbidden polyominoes” as subregions, then there exists a polynomial time algorithm for deciding a tiling.

Carolina González
Title: Grundy domination number in block graphs
Abstract: A sequence \(S = (v_1, \ldots, v_k)\) of vertices of a graph \(G\) is called dominating if \(\{v_1, \ldots, v_k\}\) is a dominating set in \(G\), and it is called legal 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 of \(G\).
Brešar 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.

In this talk we present a linear time algorithm that computes the Grundy domination number for block graphs. This result originally appeared in [2].

[1] B. Brešar, T. Gologranc, M. Milanič, D. F. Rall, R. Rizzi. Dominating sequences in graphs. Discrete Mathematics, 336:22-36, 2014.
[2] C. L. González. El problema de dominación Grundy en grafos block y grafos araña bien etiquetada. Undergraduate thesis, Universidad Nacional de Rosario, 2017.

 

Arturo Merino
Titulo: Regla azul y roja para MST con incertidumbre.
Abstract: Nos interesamos en el problema de  árbol generador de peso mínimo (MST) en un contexto donde los pesos son inciertos. Inicialmente, para cada arista e de un grafo \((V, E)\) se conocer á un conjunto no vacío \(A_e\subseteq \mathbb{R}\) que contiene los posibles pesos de la arista e. Eventualmente los “verdaderos pesos” son revelados, obteniendo un \(w_e \in A_e\) para cada arista \(e\). Diremos que un  árbol es uniformemente mínimo si es de peso mínimo sin importar cuales sean los verdaderos pesos. El problema de MST uniforme consiste en encontrar un  árbol uniformemente mínimo o determinar que ninguno existe. Mediante técnicas de minmax regret se sabe que este problema puede ser resuelto en tiempo polinomial si cada \(A_e\) es un intervalo cerrado y acotado.
Por 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ón estructural y son el motor detrás de los algoritmos de Prim, Kruskal y Boruvka.
En esta charla exploraremos una generalización de la regla azul y roja para el caso donde los pesos son inciertos. Aprovechándonos de estas nuevas ideas estructurales daremos una caracterización de la existencia de árboles uniformemente mínimos y mostraremos un nuevo algoritmo a tiempo polinomial para el problema de MST uniforme (sin restricción alguna sobre los \(A_e\)). Por  último, hablaremos de problemas relacionados que aparecen al considerar incertidumbre en los pesos.