The ACGO seminars are held every week as part of an effort of a group of researchers around the topics of Algorithms, Combinatorics, Game Theory and Optimization. Our team consists of researchers in different disciplines and from several chilean universities. If you are interested in giving a talk or receiving the announcements of the seminars, please send us an email to jverschae followed by uc.cl.

**2017-13-09:**

**Author: ** Antoine Hochart, U Chile

**Where:** Republica 779B, Sala P3, 3rd floor.

**When:** Wednesday, September 13, 14:30.

**Title:** Ergodicity of zero-sum stochastic games

**Abstract:**

Some problems related to zero-sum stochastic games (e.g. existence and characterization of the asymptotic value) can be studied by analyzing their dynamic programming operators, so called Shapley operators. In particular, when some optimality equation is solvable, then the asymptotic value exists and is independent of the initial state.

In the zero-player case (with a finite state space), that is, for finite Markov processes with rewards, the ergodicity of the Markov chain entails the solvability of the latter equation, and is characterized by several equivalent assertions. We show that most of these characterizations transpose to the two-player case.

**2017-06-09:**

**Author: ** José Fuentes, DCC, U Chile

**Where:** Republica 779B, Sala P3, 3rd floor.

**When:** Wednesday, September 06, 14:30.

**Title:** Fast and Compact Planar Embeddings

**Abstract:**

There are many representations of planar graphs, but few are as elegant as

Turán’s (1984): it is simple and practical, uses only 4 bits per edge, can handle

self-loops and multi-edges, and can store any specified embedding. Its main

disadvantage has been that it does not allow efficient searching (Jacobson,

1989). In this work we show how to add a sublinear number of bits to Turán’s

representation such that it supports fast navigation while retaining simplicity.

As a consequence of the inherited simplicity, we offer the first efficient parallel

construction of a compact encoding of a planar graph embedding. Our experi-

mental results show that the resulting representation uses about 6 bits per edge

in practice, supports basic navigation operations within a few microseconds,

and can be built sequentially at a rate below 1 microsecond per edge, featuring

a linear speedup with a parallel efficiency around 50% for large datasets.

**2017-30-08:**

**Author: ** Miquel Oliu Barton, Université Paris-Dauphine.

**Where:** Republica 779B, Sala P3, 3rd floor.

**When:** Wednesday, August 30, 14:30.

**Title:** The unknown stochastic game

**Abstract:**

Stochastic games are the simplest model of dynamic games, introduced by Shapley in 1953: to every state corresponds a game, and the transition from state to state is jointly controlled by the players. But what do the players know about the parameters of the model?

**2017-23-08:**

**Author: ** Jannik Matuschke, TU Munich.

**Where:** Republica 779B, Sala P3, 3rd floor.

**When:** Wednesday, August 23, 14:30.

**Title:** The Complexity of Computing a Robust Flow

**Abstract:**

Robust network flows are a concept for dealing with uncertainty and unforeseen failures in the network infrastructure. One of the most basic models is the Maximum Robust Flow Problem: Given a network and an integer k, the task is to find a path flow of maximum robust value, i.e., the guaranteed value of surviving flow after removal of any k arcs in the network. The complexity of this problem appeared to have been settled almost a decade ago: Aneja et al. (2001) showed that the problem can be solved efficiently when k = 1, while an article by Du and Chandrasekaran (2007) established that the problem is NP-hard for any constant value of k larger than 1.

We point to a flaw in the proof of the latter result, leaving the complexity for constant k open once again. For the case that k is not bounded by a constant, we present a new hardness proof, establishing that the problem is strongly NP-hard, even when only two different capacity values occur and the number of paths is polynomial in the size of the input. We further show that computing optimal integral solutions is already NP-hard for k = 2 (whereas for k=1, an efficient algorithm is known) and give a positive result for the case that capacities are in {1, 2}.

This is joint work with Yann Disser (TU Darmstadt).

**2017-16-08:**

**Author: ** Sebastian Berndt, U Lubeck.

**Where:** Republica 779B, Sala P3, 3rd floor.

**When:** Wednesday, August 16, 14:30.

**Title:** The PACE challenge: practical algorithms for tree width

**Abstract:**

While the theoretical aspects concerning the computation of tree width -

one of the most important graph parameters – are well understood, it is

not clear how it can be computed practically. As tree width has a wide

range of applications, e.g. in bioinformatics or artificial

intelligence, this lack of understanding hinders the applicability of

many important algorithms in the real world. The Parameterized

Algorithms and Computational Experiments (PACE) challenge therefore

chose the computation of tree width as one of its challenge problems in

2016 and again in 2017. In 2016, Hisao Tamaki (Meiji University)

presented a new algorithm that outperformed the other approaches (SAT

solver and branch-and-bound) by far. Although no theoretical performance

guarantees for his algorithm are known, it was so dominating that all

participants in 2017 used a variant of Tamaki’s algorithm. This allowed

the winning implementation due to Larisch (King-Abdullah University of

Science and Engineering) and Salfelder (University of Leeds) to solve

over 50% of the test suite (containing graphs with over 3500 nodes) in

under six seconds. Before PACE 2016, no algorithm was known to reliably

compute tree width on graphs with about 100 nodes. Acknowledging this

fact, Tamaki’s paper on his algorithm won the best paper award in track

B of ESA 2017.

In this talk, I will first give a gentle introduction to tree width,

parameterized algorithms and the PACE challenge. I will then present a

streamlined version of Tamaki’s algorithm based on a variant of the

well-studied cops-and-robber game. This allows us to produce hard

instances for the algorithm, derive the first known upper bound on its

running time and give a plausible conjecture explaining its practical

performance.

This talk is based on joint work with Max Bannach (University of

Luebeck).

**2017-09-08:**

**Author: ** Marc Schroder, U Chile.

**Where:** Republica 779B, Sala P3, 3rd floor.

**When:** Wednesday, August 09, 14:30.

**Title:** Network congestion games are robust for variable demand

**Abstract:**

Network congestion games have provided a fertile ground for the algorithmic game theory community. Indeed, many of the pioneering works on bounding the efficiency of equilibria use this framework as their starting point. In recent years, there has been an increased interest in studying randomness in this context, with a particular focus on understanding what happens when link latencies are subject to random shocks. We assume that the source of randomness is the inherent variability of the demand that most practical networks suffer from. Therefore, in this paper we look at the basic nonatomic network congestion game with the additional feature that demand is random. The first obstacle we have to sort out is the definition of equilibrium, as the classic concept of Wardrop equilibrium needs to be extended to the random demand setting. Interestingly, Wang, Doan, and Chen (2014), by considering an equilibrium notion in which flow particles evaluate their expected cost using the full knowledge of the demand distribution, conclude that the price of anarchy of the game can be arbitrarily large. In contrast, our main result in this paper is that under a very natural equilibrium notion, in which the basic behavioral assumption is that users evaluate their expected cost according to the demand they experience in the system, the price of anarchy of the game is actually the same as that in the deterministic demand game.

**2017-02-08:**

**Author: ** Patricio Foncea, U Chile.

**Where:** Republica 779B, Sala P3, 3rd floor.

**When:** Wednesday, August 02, 14:30.

**Title:** Prophet Inequalities and applications in Mechanism Design

**Abstract:**

The classic prophet inequality states that, when faced to a finite sequence of non-negative independent random variables, a gambler who knows their distribution and is allowed to stop the sequence at any time, can obtain, in expectation, at least half as much reward as a prophet who knows the values of each random variable and can choose the largest one. In this work we study a modified version of the previous problem, where the random variables are presented in uniform random order and the stop rule must be decided before hand (i.e., the gambler cannot adapt its strategy). We prove that a factor of 1-1/e is achievable with respect to the expected maximum, and that this value is tight.

As an application of these results, we provide a reduction to posted price mechanisms, where an auction takes place with customers arriving sequentially and being offered a take-it-or-leave-it price for the item. We prove that if such mechanism is not allow to adapt the prices offered and the customers arrive in random order, then its expected revenue guarantees the same tight bound with respect to the expected revenue of the optimal auction.

**2017-12-07:**

**Author: ** Tjark Vredeveld, U Maastricht.

**Where:** Republica 779B, Sala P3, 3rd floor.

**When:** Wednesday, July 12, 14:30.

**Title:** Using stochastic dominance in the comparison of online algorithms.

**Abstract:**

The standard way to assess the quality of online algorithms is competitive analysis. However, as it is a worst-case performance measure, it has been criticised as being too pessimistic or not able to discriminate between different algorithms. A good example for this is the paging problem, in which all so-called marking algorithms are k-competitive (where k is the number of pages in the fast memory).

Several variants have been proposed to deal with this criticism. In this talk, I will discuss the method of stochastic dominance to compare online algorithms. For example, for the paging algorithm, we have shown that under some assumptions of locality of reference, an online algorithm known as Least Recently Used outperforms any other online algorithm.

This talk is based on joint work with Benjamin Hiller (Zuse Institute Berlin).

**2017-21-06:**

**Author: ** Fabio Botler, DII, U Chile.

**Where:** Republica 779B, Sala P3, 3rd floor.

**When:** Wednesday, June 21, 14:30.

**Title:** Two conjectures on decompositions of graphs into paths and cycles.

**Abstract:**

A path (resp. cycle) decomposition of a graph G is a set of edge-disjoint paths (resp. cycles) of G that covers the edge-set of G. Gallai (1966) conjectured that every graph on n vertices admits a path decomposition of size at most (n + 1)/2, and Hajós (1968) conjectured that every Eulerian graph on n vertices admits a cycle decomposition of size at most (n − 1)/2. Although these conjectures seem similar, they were verified for distinct classes of graphs. For example, Gallai’s Conjecture was verified for graphs with no cycle composed only by even degree vertices, while Hajós’ Conjecture was verified for graphs with maximum degree at most 4, and for planar graphs. In this talk, I will present a technique that allowed us to verify both conjectures for some (new and old) classes of graphs. We verify both Gallai’s and Hajós’ Conjectures for series–parallel graphs; for graphs with maximum degree 4; and for graphs with treewidth at most 3. Moreover, we show that the only graphs in these classes that do not admit a path decomposition of size at most n/2 are isomorphic to K_3 , K_5 or K_5 – e.

**2017-14-06:**

**Author: ** Sergio Rica, UAI Physics Center, UAI.

**Where:** Republica 779B, Sala P3, 3rd floor.

**When:** Wednesday, June 14, 14:30.

**Title:** Thermodynamics of small systems through a reversible and conservative discrete automaton.

**Abstract:**

The focus of this talk will be the Q2R model which is a reversible and conservative cellular automaton. The Q2R model possesses quite a rich and complex dynamics. Indeed, the configuration space is composed of a huge number of cycles with exponentially long periods, that we attempt to characterize. Furthermore, a coarse-graining approach is applied to the time series of the total magnetization, leading to a master equation that governs the macroscopic irreversible dynamics of the Q2R automata. The methodology is replicated for various system sizes. In the case of small systems, we show that the master equation leads to a tractable probability transfer matrix of moderate size, which provides a consistent and tractable thermodynamic description. This work is in collaboration with Felipe Urbina and Marco Montalva.

**2017-07-06:**

**Author: ** Pedro Montealegre, UAI.

**Where:** Republica 779B, Sala P3, 3rd floor.

**When:** Wednesday, June 7, 14:30.

**Title:** Graph Reconstruction in the Congested Clique

**Abstract:**

The congested clique model is a message-passing model of distributed computation where the underlying communication network is the complete graph of $n$ nodes. In this talk we consider the situation where the joint input to the nodes is an $n$-node labeled graph $G$, i.e., the local input received by each node is a line of the adjacency matrix of $G$. Nodes execute an algorithm, communicating with each other in synchronous rounds and their goal is to compute some function that depends on $G$.

The most difficult problem we could attempt to solve is the reconstruction problem, where nodes are asked to recover all the edges of the input graph $G$. Formally, given a class of graphs $\mathcal{G}$, the problem is defined as follows: if $G$ is not in $\mathcal{G}$, then every node must reject; on the other hand, if $G$ belongs to $\mathcal{G}$, then every node must end up knowing all the edges of $G$. It is not difficult to see that the total number of bits received by a node through one link is at least $\Omega(\log|\mathcal{G}_n|/n)$, where $\mathcal{G}_n$ is the subclass of all $n$-node labeled graphs in $\mathcal G$.

In this talk we prove that previous bound is tight and that it is possible to achieve it with only two rounds. Moreover, it this bound can be archeived for hereditary classes of graphs in one round. This result recover all known algorithms concerning the reconstruction of graph classes in one round and bandwidth $\cO(\log n)$: forests, planar graphs, cographs, etc. But we also get new one-round algorithms for other hereditary graph classes such as unit disc graphs, interval graphs, etc.

**2017-31-05:**

**Author: ** Diego Arroyuelo, Informatics Department, UTFSM.

**Where:** Republica 779B, Sala P3, 3rd floor..

**When:** Wednesday, May 31, 14:30.

**Title:** Data-aware measures for the dictionary problem.

**Abstract:** Given a sorted set S of size n from a universe U = {1, 2, …, u}, the dictionary problem consists of constructing a data structure for S such that the following queries are supported efficiently: rank (which given a universe element x, counts the number of elements in S that are smaller or equal than x), select (which given a value j, obtains the j-th element in the sorted set S), and member (which test whether a given element belongs to S or not).

Dictionaries are a fundamental building block for many applications in computer science (compressed data structures, information retrieval, text compression), biology (compression of biological sequences), and physical sciences (data collection from particle colliders), among others. Many of these applications are data-intensive, hence the compressed representation of dictionaries becomes crucial.

There exist several compression models for dictionaries, each model defining a compression measure. Such a measure is simply a formula that indicates the minimum amount of bits one could achieve for the representation of set S using that model. In particular, data-aware measures are those that take advantage of the distribution of the n elements in the set to improve compression.

This talk will survey the best known data-aware measures for dictionary compression, as well as the corresponding data structures to support operations rank, select, and member. This will be followed by a discussion about the need of new data-aware measures that achieve better compression in certain circumstances that are of practical relevance. The talk will end proposing a preliminary definition of such a measure, and then a discussion on the consequences of this definition.

**2017-24-05:**

**Author: ** Retsef Levi, MIT Sloan School of Management.

**Where:** Beauchef Poniente (new building), Torre Oriente, 4th Floor, Sala Seminario DII.

**When:** Wednesday, May 24, 14:30.

**Title:** Exploration vs. Exploitation: Reducing Uncertainty in Operational Problems

**Abstract:** Motivated by several core operational applications, we introduce a new class of multistage stochastic optimization models that capture a fundamental tradeoff between performing work and making decisions under uncertainty (exploitation) and investing capacity (and time) to reduce the uncertainty in the decision making (exploration). Unlike existing models, in which the exploration-exploitation tradeoffs typically relate to learning the underlying distributions, the models we introduce assume a known probabilistic characterization of the uncertainty, and focus on the tradeoff of learning (or partially learning) the exact realizations.

For several interesting scheduling models we derive insightful structural results on the optimal policies that lead not only to quantification of the value of learning, but also obtain surprising optimal local decision rules for when it is optimal to explore (learn).

The talk is based on several papers that are joint work with Chen Attias, Tom Magnanti, Robi Krauthgamer and Yaron Shaposhnik.

**2017-17-05:**

**Author: ** Carlos Ochoa, DCC, U Chile.

**Where:** Republica 779B, Sala P3, 3rd floor.

**When:** Wednesday, May 17, 14:30.

**Title:** Synergistic Solutions on MultiSets

**Abstract:** Karp et al. (1988) described Deferred Data Structures for Multisets as “lazy” data structures which partially sort data to support online rank and select queries, with the minimum amount of work in the worst case over instances of size $n$ and number of queries $q$ fixed. Barbay et al. (2016) refined this approach to take advantage of the gaps between the positions hit by the queries (i.e., the structure in the queries). We develop new techniques in order to further refine this approach and take advantage all at once of the structure (i.e., the multiplicities of the elements), some notions of local order (i.e., the number and sizes of runs) and global order (i.e., the number and positions of existing pivots) in the input; and of the structure and order in the sequence of queries. Our main result is a synergistic deferred data structure which outperforms all solutions in the comparison model that take advantage of only a subset of these features. As intermediate results, we describe two new synergistic sorting algorithms, which take advantage of some notions of structure and order (local and global) in the input, improving upon previous results which take advantage only of the structure (Munro and Spira 1979) or of the local order (Takaoka 1997) in the input; and one new multiselection algorithm which takes advantage of not only the order and structure in the input, but also of the structure in the queries.

**2017-03-05:**

**Author: ** Patricio Poblete, DCC, U Chile.

**Where:** Republica 779B, Sala P3, 3rd floor.

**When:** Wednesday, May 03, 14:30.

**Title:** Robin Hood Hashing really has constant average search cost and variance in full tables

**Abstract:** Thirty years ago, the Robin Hood collision resolution strategy was introduced for open addressing hash tables, and a recurrence equation was found for the distribution of its search cost. Although this recurrence could not be solved analytically, it allowed for numerical computations that, remarkably, suggested that the variance of the search cost approached a value of $1.883$ when the table was full. Furthermore, by using a non-standard mean-centered search algorithm, this would imply that searches could be performed in expected constant time even in a full table.

In spite of the time elapsed since these observations were made, no progress has been made in proving them. In this paper we introduce a technique to work around the intractability of the recurrence equation by solving instead an associated differential equation. While this does not provide an exact solution, it is sufficiently powerful to prove a bound for the variance, and thus obtain a proof that the variance of Robin Hood is bounded by a small constant for load factors arbitrarily close to 1. As a corollary, this proves that the mean-centered search algorithm runs in expected constant time.

We also use this technique to study the performance of Robin Hood hash tables under a long sequence of insertions and deletions, where deletions are implemented by marking elements as deleted. We prove that, in this case, the variance is bounded by 1/(1-alpha)+O(1), where alpha is the load factor.

To model the behavior of these hash tables, we use a unified approach that we apply also to study the First-Come-First-Served and Last-Come-First-Served collision resolution disciplines, both with and without deletions.

**2017-26-04:**

**Author: ** Pablo Marquet, PUC.

**Where:** Republica 779B, Sala P3, 3rd floor.

**When:** Wednesday, April 24, 14:30.

**Title:** What will be the impact of climate change on biodiversity (us included): An open and hot problem.

**2017-12-04:**

**Author: ** Marc Schroder, U Chile.

**Where:** Republica 779B, Sala P3, 3rd floor.

**When:** Wednesday, April 12, 14:30.

**Title:** Claim games for estate division problems

**Abstract:** The estate division problem, also known as bankruptcy problem, concerns the issue of dividing an estate among a group of claimants when the sum of entitlements exceeds the size of the estate. This problem was formally introduced by O’Neill (1982), after which most of the literature focused on comparing different solution rules by means of their properties. We approach the problem strategically and analyse the claim game that is initiated by O’Neill (1982).

**2017-04-04:**

**Author: ** Jie Han, Universidade de Sao Paulo.

**Where:** Republica 779B, Sala P3, 3rd floor.

**When:** Wednesday, April 05, 14:30.

**Title:** Perfect Matchings in Hypergraphs

**Abstract:** The problem of determining the minimum d-degree threshold for finding a perfect matching in k-uniform hypergraphs has attracted much attention in the last decade. It is also closely related to the Erdös Matching Conjecture back to 1960s. We will introduce the problem, survey the existing results, and mention some recent progress.

**2017-29-03:**

**Author: ** Kevin Schewior, U Chile.

**Where:** Republica 779B, Sala P3, 3rd floor.

**When:** Wednesday, March 29, 14:30.

**Title:** Chasing Convex Bodies

**Abstract:** We consider the following online problem in d-dimensional Euclidean space. The server initially located in the origin receives an online sequence of convex bodies. In response to each body, the task is to move to a point within that body so as to minimize the total moved distance. We evaluate the performance of online algorithms by competitive analysis. This problem was first considered by Friedman and Linial in 1993 and is an interesting special case of the very general online problem of metrical task systems. Friedman and Linial gave a rather involved constant-competitive algorithm for d=2.

We first look at different greedy policies and notice that they are not constant-competitive even when d=2 and all convex bodies are lines. We then develop a nevertheless simple new algorithm for this special case. Applying a sequence of known and new reductions, we are able to extend this result to a 2^O(d)-competitive algorithm when d is arbitrary and all convex bodies are affine subspaces of the full space. This is the first constant-competitive algorithm in this setting with fixed d>2.

Finally, we discuss directions for future research: Closing the gap between 2^O(d) and the simple lower bound sqrt(d), considering general convex-body chasing, and considering convex-function chasing which is an intermediate problem between convex-body chasing and metrical task systems.

**2017-22-03:**

**Author: ** Krzysztof Fleszar, U Chile.

**Where:** Republica 779B, Sala P3, tercer piso.

**When:** Wednesday, March 22, 14:30.

**Title:** Maximum Disjoint Paths: New Algorithms based on Tree-Likeness

**Abstract:** Maximum Edge Disjoint Paths is a classical NP-hard problem of finding a

maximum-size subset from a given set of k terminal pairs that can be

routed via edge-disjoint paths.

One of the big open problems in approximation algorithms is to close the

gap between the best known approximation upper bound of $\sqrt{n}$

(Chekuri et al. (2006)) and the best known lower bound of $2^{\sqrt{\log

n}}$ (Chuzhoy et al. (2016)). In their seminal paper, Raghavan and

Thompson (Combinatorica, 1987) introduce the technique of randomized

rounding for LPs; their technique gives an O(1)-approximation when edges

may be used by $O(\log n / \log\log n)$ paths.

In this talk, I introduce the problem and present two of our algorithms

(ESA 2016) that strengthen the fundamental results above. They provide

new bounds formulated in terms of the feedback vertex set number r of a

graph, which measures its vertex deletion distance to a forest.

- An $O(\sqrt{r} \log{kr})}$-approximation algorithm. Up to a

logarithmic factor, it strengthens the best known ratio $\sqrt{n}$ due

to Chekuri et al., as $r \le n$.

- An $O(1)$-approximation algorithm with congestion bounded by

$O(\log{kr} / \log\log{kr})$, strengthening the bound obtained by the

classic approach of Raghavan and Thompson.

At the end, an open problem will be stated.

**2017-15-03:**

**Author: ** Saeed Hadikanloo, Univ. de Paris 9.

**Where:** Republica 779B, Sala P3, tercer piso.

**When:** Wednesday, March 15, 14:30.

**Title:** Learning in NonAtomic Anonymous Games: Application to First Order Mean Field Games

**Abstract:**

We introduce a model of anonymous games where the actions are chosen from possibly player dependent sets. We propose several learning procedures similar to the well-known Fictitious Play and Online Mirror Descent and prove their convergence to equilibrium under the classical monotonicity condition. Typical examples are First Order Mean Field Games.

**Previous Years**