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.

**2019-04-12:**

**Author: ** Matías Villagra, PUC

**Where:** Av República 701,** Sala 22**.

**When:** Wednesday, December 4, **14:30**.

**Title:** An efficient symmetry breaking technique for arbitrary groups

**Abstract: ** Symmetries are commonly found in Integer Linear Programs (ILPs) or in some of their substructures. Having many symmetric solutions could make common algorithms as branch-and-bound inefficient, hence breaking symmetries might yield important gains.

Given a group of symmetries of an ILP, a Fundamental Domain is a set of R^n that aims to select a unique representative of symmetric vectors, i.e. such that each point in the set is a unique representative under its G-orbit, effectively breaking all symmetries of the group. The canonical Fundamental Domain found in the literature, which can be constructed for any permutation group, is NP-hard to separate even for very simple groups, whose elements are disjoint involutions (Babai & Luks 1983).

In this talk I will introduce basic group theoretical tools to show that for every finite permutation group there exists a Fundamental Domain which has quadratic many facets on the dimension, hence the separation problem for this particular Fundamental Domain can be done in polynomial time. Even more, this implies that for a given group there exist different types of Fundamental Domains, some of which can be separated in polytime while others cannot. In particular, intersecting a given polytope with different Fundamental Domains (for a fixed group), might yield polytopes with radically different extension complexity.

This is joint work with José Verschae and Léonard von Niederhäusern.

**2019-13-11:**

**Author: ** Tim Oosterwijk, Maastricht U.

**Where:** Av República 701, Sala 33.

**When:** Wednesday, November 27, **14:30**.

**Title:** On the Price of Anarchy for Flows over Time

**Abstract: **Dynamic network flows, or network flows over time, constitute an important model for real-world situations where steady states are unusual, such as urban traffic and the Internet. In order to describe the temporal evolution of such systems one has to consider the propagation of flow across the network by tracking the position of each particle along time. These applications immediately raise the issue of analyzing dynamic network flows from a game-theoretic perspective.

In this talk I will discuss dynamic equilibria in the deterministic fluid queuing model in single-source single-sink networks, arguably the most basic model for flows over time. I will then present the main ideas behind the result that if we could reduce the inflow of the network in a dynamic equilibrium, then the Price of Anarchy is bounded by a factor, parameterized by the longest path length, that converges to e/(e-1) = 1.582. I will mention some other results we found and finish with some intriguing open questions.

This is joint work with José Correa and Andrés Cristi.

**2019-13-11:**

**Author: ** Alexandros Tsigonias-Dimitriadis, TU Munich.

**Where:** Av República 701, Sala 33.

**When:** Wednesday, November 20, **14:30**.

**Title:** Robust Revenue Maximization Under Minimal Statistical Information

**Abstract: **We study the problem of multi-dimensional revenue maximization when selling $m$ items to a buyer that has additive valuations for them, drawn from a (possibly correlated) prior distribution. Unlike traditional Bayesian auction design, we assume that the seller has a very restricted knowledge of this prior: they only know the mean $\mu_j$ and an upper bound $\sigma_j$ on the standard deviation of each item’s marginal distribution. Our goal is to design mechanisms that achieve good revenue against an ideal optimal auction that has full knowledge of the distribution in advance. Informally, our main contribution is a tight quantification of the interplay between the dispersity of the priors and the aforementioned robust approximation ratio. Furthermore, this can be achieved by very simple selling mechanisms.

More precisely, we show that selling the items via separate price lotteries achieves an $O(\log r)$ approximation ratio where $r=\max_j(\sigma_j/\mu_j)$ is the maximum coefficient of variation across the items.If forced to restrict ourselves to deterministic mechanisms, this guarantee degrades to $O(r^2)$. Assuming independence of the item valuations, these ratios can be further improved by pricing the full bundle. For the case of identical means and variances, in particular, we get a guarantee of $O(\log(r/m))$ which converges to optimality as the number of items grows large. We demonstrate the optimality of the above mechanisms by providing matching lower bounds.

This is joint work with Yiannis Giannakopoulos and Diogo Poças.

**2019-13-11:**

**Author: ** Waldo Galvez, IDSIA.

**Where:** Av República 701, Sala 33.

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

**Title:** On the Cycle Augmentation Problem: Hardness and Approximation

Algorithms

**Abstract: **In the k-Connectivity Augmentation Problem we are given a

k-edge-connected graph and a set of additional edges called links. Our

goal is to find a set of links of minimum cardinality whose addition

to the graph makes it (k+1)-edge-connected. There is an approximation

preserving reduction from the mentioned problem to the case k=1

(a.k.a. the Tree Augmentation Problem or TAP) or k=2 (a.k.a. the

Cactus Augmentation Problem or CacAP). While several better-than-2

approximation algorithms are known for TAP, nothing better is known

for CacAP (hence for k-Connectivity Augmentation in general).

As a first step towards better approximation algorithms for CacAP, we

consider the special case where the input cactus consists of a single

cycle, which we call the Cycle Augmentation Problem (CycAP). This

apparently simple special case retains part of the hardness of the

general case. In particular, we are able to show that it is APX-hard.

In this talk we present a combinatorial (3/2+eps)-approximation for

CycAP. We also present an LP formulation with a matching integrality

gap, which might be useful to address the general case of the problem.

This is joint work with Fabrizio Grandoni, Afrouz Jabal Ameli and

Krzysztof Sornat.

**2019-09-10:**

**Author: ** Laurent Feuilloley, DII, U Chile.

**Where:** Av República 701, Sala 22.

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

**Title:** Graph classes and forbidden patterns on three vertices

**Abstract:**

Many graph classes have a characterization of the following shape: there should exist an ordering of the vertices such that the ordered graph avoids some pattern. For example, a graph is a forest if and only if one can order the vertices such that no node has more than one neighbor on its right.

I will discuss this type of characterization, and in particular our result which is a list of the classes that can be characterized by an ordering avoiding such pattern on three vertices. This list includes many interesting classes such as interval, threshold and chordal graphs, and we can derive various structural properties from this ordering point of view.

This is joint work with Michel Habib.

**2019-09-10:**

**Author: ** Patrick Morris, Freie U, Berlin

**Where:** Av República 701, Sala 33.

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

**Title:** Extending Ryser’s conjecture to t-intersecting hypergraphs

**Abstract:**

A well-known conjecture, often attributed to Ryser, states that every r-partite r-uniform hypergraph has cover number at most (r-1) times its matching number. Despite considerable effort, this conjecture remains wide open, motivating the pursuit of variants of the original conjecture. Recently, Király and Tóthmérész, and independently Bustamente and Stein, considered the problem under the assumption that the hypergraph is $t$-intersecting, conjecturing that the cover number $\tau(\mathcal{H})$ of such a hypergraph H is at most r-t. This conjecture was proven for all r <= 4t-1.

We extend this result in two directions. First, for r <= 3t-1, we prove a tight upper bound on the cover number of these hypergraphs, showing that they in fact satisfy $\tau(\mathcal{H}) \leq \floor{(r – t)/2} + 1$ and there is a matching construction. Second, we extend the range of t for which the conjecture is known to be true, showing that it holds for all r < (36t)/7-5. In this talk we will discuss these results and some of the ideas behind their proofs.

This represents joint work with Anurag Bishnoi, Shagnik Das and Tibor Szabó.

**2019-04-09:**

**Author: ** Victor Verdugo, UOH & LSE

**Where:** Av República 701, Sala 33.

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

**Title:** Convex hierarchies, scheduling and symmetries

**Abstract:**

The Sum of Squares (SoS) hierarchy provides a finite nested family K_1, K_2, … , K_n of convex relaxations for an integer program with n variables, that reaches the integer hull, i.e., K_n corresponds to the convex hull of the integer feasible solution. A natural question is to understand how the integrality gap evolves over the family. In particular, a rapid decay of the gap might yield good approximation algorithms. We show that for the classic problem of scheduling identical machines to minimize the makespan, the SoS hierarchy exhibits an integrality gap curve that remains at least 1+ delta, for some small delta > 0, for K_j when j is linear on the number of jobs. In contrast, this problem admits polynomial time approximation schemes. In this talk I will (a) highlight the main ideas behind the construction of the lower bounds, and time permitting (b) explain why symmetries are in this case the main issue.

**2019-21-08:**

**Author: ** Penny Haxell, University of Waterloo

**Where:** Av República 701, Sala 33.

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

**Title:** Algorithms for independent transversals vs. small dominating sets

**Abstract:**

An {\it independent transversal} (IT) in a vertex-partitioned graph

$G$ is an independent set in $G$ consisting of one vertex in each

partition class. There are

several known criteria that guarantee the

existence of an IT, of the following general form: the graph

$G$ has an IT unless the subgraph $G_S$ of $G$, induced by the union of some

subset $S$ of vertex classes, has a small dominating set. These

criteria have been used over the years to solve many combinatorial problems.

The known proofs of these IT theorems do not give efficient

{\it algorithms}

for actually finding an IT or a subset $S$ of classes such that $G_S$

has a small dominating set. Here we present appropriate weakenings of

such results that do have effective proofs. These result in

algorithmic versions of many of the original applications of IT

theorems. We will discuss a few of these here, including hitting sets

for maximum cliques, circular edge colouring of bridgeless cubic

graphs, and hypergraph matching problems.

**2019-14-08:**

**Author: ** Alonso Herrera, U Andrés Bello.

**Where:** Av República 701, Sala 33.

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

**Title:** Complexity of point-to-planar convex set distance

**Abstract:**

In computer science, there are several equivalent ways to define a com-

putable compact set in $\R^k$. One of them is the so called “locally com-

putable compact set”, that is, being able to decide whether or not a given

ball intersects the set – this is often referred to as the “pixel information” of

the set because, loosely speaking, it allows us to know which pixels must be

coloured when drawing a picture of the set on a screen. It is not hard to see

that from the pixel information of a set one can compute the distance to a

given point, but the computational cost of doing so may be very different for

different sets.

In this talk we discuss the computational complexity of point-to-set dis-

tance restricted to planar convex bounded sets using a geometrical approach.

In particular we will show that in this case there is an algorithm to compute

this distance in polynomial time.

This is a joint work with M. Hoyrup.

**2019-31-07:**

**Author: ** Simon Piga, U Hamburg.

**Where:** Av República 701, Sala 33.

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

**Title:** Tight Hamiltonian Cycles in uniformly dense Hypergraphs

**Abstract:**

We study sufficient conditions for the existence of Hamiltonian cycles in uniformly dense $3$-uniform hypergraphs. Problems of this type were first considered by Lenz, Mubayi, and Mycroft for loose Hamiltonian

cycles and Aigner-Horev and Levy considered it for tight Hamiltonian cycles for a fairly strong notion of uniformly dense hypergraphs. We focus on tight cycles and obtain optimal results for a weaker notion of uniformly dense hypergraphs. We show that if an $n$-vertex $3$-uniform hypergraph $H=(V,E)$ has the property that for any set of vertices $X$ and for any collection $P$ of pairs of vertices, the number of hyperedges composed by a pair belonging to $P$ and one vertex from $X$ is at least $(1/4+o(1))|X||P| – o(|V|^3)$ and $H$ has minimum vertex degree at least $\Omega(|V|^2)$, then $H$ contains a tight Hamiltonian cycle. A probabilistic construction shows that the constant $1/4$ is optimal in this context.

**2019-24-07:**

**Author: ** Ivan Rapaport, DIM-CMM, U de Chile.

**Where:** Av República 701, Sala 33.

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

**Title:** On Distributed Merlin-Arthur Decision Protocols

**Abstract:**

In a distributed locally-checkable proof, we are interested in checking the legality of a given network configuration with respect to some Boolean predicate. To do so, the network enlists the help of a prover — a computationally-unbounded oracle that aims at convincing the network that its state is legal, by providing the nodes with certificates that form a distributed proof of legality. The nodes then verify the proof by examining their certificate, their local neighborhood and the certificates of their neighbors.

In this talk we examine the power of a randomized form of locally-checkable proof, called distributed Merlin-Arthur protocols, or dMA for short. In a dMA protocol, the prover assigns each node a short certificate, and the nodes then exchange random messages with their neighbors. We show that while there exist problems for which dMA protocols are more efficient than protocols that do not use randomness, for several natural problems, including Leader Election, Diameter, Symmetry, and Counting Distinct Elements, dMA protocols are no more efficient than standard nondeterministic protocols. This is in contrast with Arthur- Merlin (dAM) protocols and Randomized Proof Labeling Schemes (RPLS), which are known to provide improvements in certificate size, at least for some of the aforementioned properties.

Joint work with Pierre Fraigniaud, Pedro Montealegre, Rotem Oshman and Ioan Todinca.

**2019-10-07:**

**Author: ** Christoph Hunkenschroeder, EPFL.

**Where:** Av República 701, Sala 33.

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

**Title:** Recognizing the rotated standard lattice

**Abstract:**

Let B be a set of linearly independent vectors. The Euclidean lattice L spanned by B is the set of all integral linear combinations of the vectors in B. Lattices play an important role in several areas of mathematics, for instance Integer Programming, or Cryptography. An important problem on lattices is the Closest Vector Problem: given a lattice basis B and a target vector t in the linear span of B, what is the lattice point closest to t?

Though being NP-hard in general, the problem becomes trivial if the lattice spanned by B is the standard lattice Z^n, which can be verified easily.

However, if B does not generate Z^n itself but a rotation thereof, it is still open how this can efficiently be recognized.

In this talk, I will introduce all necessary terms and derive this open question while naming some related problems and results known from the literature on the way. In the end, I will give some small partial results, hoping to wake your interest in this problem.

**2019-26-06:**

**Author: ** Gweneth McKinley, MIT

**Where:** Av República 701, Sala 33.

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

**Title:** Super-logarithmic cliques in dense inhomogeneous random graphs

**Abstract:**

In the theory of dense graph limits, a graphon is a symmetric measurable function W from [0,1]^2 to [0,1]. Each graphon gives rise naturally to a random graph distribution, denoted G(n,W), that can be viewed as a generalization of the Erdos-Renyi random graph. Recently, Dolezal, Hladky, and Mathe gave an asymptotic formula of order log(n) for the size of the largest clique in G(n,W) when W is bounded away from 0 and 1. We show that if W is allowed to approach 1 at a finite number of points, and displays a moderate rate of growth near these points, then the clique number of G(n,W) will be of order √n almost surely. We also give a family of examples with clique number of order n^c for any c in (0,1), and some conditions under which the clique number of G(n,W) will be o(√n) or omega(√n). This talk assumes no previous knowledge of graphons.

**2019-19-06:**

**Author: ** Daniel Dadush, CWI.

**Where:** Av República 701, Sala 33.

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

**Title:** Balancing Vectors in any Norm

**Abstract:**

In the vector balancing problem, we are given symmetric convex bodies C and K in R^n, and our goal is to determine the minimum number β ≥ 0, known as the vector balancing constant from C to K, such that for any sequence of vectors in C there always exists a signed combination of them lying inside βK. Many fundamental results in discrepancy theory, such as the Beck-Fiala theorem (Discrete Appl. Math ‘81), Spencer’s “six standard deviations suffice” theorem (Trans. Amer. Math. Soc ‘85) and Banaszczyk’s vector balancing theorem (Random Structures & Algorithms ‘98) correspond to bounds on vector balancing constants.

The above theorems have inspired much research in recent years within theoretical computer science, from the development of efficient polynomial time algorithms for matching existential vector balancing guarantees, to their applications in the context of approximation algorithms. In this work, we show that all vector balancing constants admit “good” approximate characterizations, with approximation factors depending only polylogarithmically on the dimension n. First, we show that a volumetric lower bound due to Banaszczyk is tight within a O(log n) factor. Our proof is algorithmic, and we show that Rothvoss’s (FOCS ‘14) partial coloring algorithm can be analyzed to obtain these guarantees. Second, we present a novel convex program which encodes the “best possible way” to apply Banaszczyk’s vector balancing theorem for bounding vector balancing constants from above, and show that it is tight within an O(log^{2.5} n) factor. This also directly yields a corresponding polynomial time approximation algorithm both for vector balancing constants, and for the hereditary discrepancy of any sequence of vectors with respect to an arbitrary norm.

**2019-12-06:**

**Author: ** Andrew Xia, MIT.

**Where:** Av República 701, Sala 33.

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

**Title:** Efficient Implementation of a Practical Leakage-Resilient ID Scheme

**Abstract:**

Instead of viewing cryptographic algorithms as simple black-boxes, leakage-resilient cryptography accepts that certain traditionally secret parts of the algorithm will be available to the attacker through side channel attacks and aims to ensure the security of these algorithms in the presence of such leakage. We present a leakage resilient identification scheme based on the continuous memory leakage model, which assumes that the leakage of information is unrestricted in time and space. We design a three message sigma protocol, secure under the symmetric external diffie-hellman (SXDH) assumption, using pairings-based elliptic curve cryptography.

This is joint work with Chiraag Juvekar, Utsav Banerjee, Yael Kalai, and Anantha Chandrakasan.

I will present this talk such that minimal background with cryptography is necessary.

**2019-15-05:**

**Author: ** Felix Joos, University of Birmingham.

**Where:** Av República 701, Sala 33.

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

**Title:** Graph decompositions using group actions

**Abstract:** I will present some recent results on graph decompositions. To this end, we find a very `nice’ subgraph H in a host graph we would like to decompose into copies of H. Then we employ a group action to `rotate’ H. This rotation yields a decomposition of the host graph into copies of H. We construct this `nice’ subgraph using probabilistic tools, a well-known hypergraph matching theorem due to Pippenger and Spencer and an absorption method. This is joint work with Stefan Ehard and Stefan Glock.

**2019-08-05:**

**Author: ** Pierre Aboulker, U. Nice-Sophia-Antipolis.

**Where:** Av República 701, Sala 33.

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

**Title:** Generalizations of the geometric de Bruijn Erdős Theorem

**Abstract:** A classic Theorem of de Bruijn and Erdős states that every noncollinear set of n points in the plane determines at least n distinct lines. The line L(u, v) determined by two points u, v in the plane consists of all points p such that

• dist(p, u) + dist(u, v) = dist(p, v) (i.e. u is between p and v) or

• dist(u, p) + dist(p, v) = dist(u, v) (i.e. p is between u and v) or

• dist(u, v) + dist(v, p) = dist(u, p) (i.e. v is between u and p).

With this definition of line L(uv) in an arbitrary metric space (V, dist), Chen

and Chvátal conjectured that every metric space on n points, where n is at least 2, has at least n distinct lines or a line that consists of all n points. The

talk will survey results on and around this conjecture.

**2019-17-04:**

**Author: ** Tobias Mömke, Saarland University.

**Where:** Av República 701, Sala 33.

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

**Title:** Finding 2-factors without triangles

**Abstract:** A 2-factor is a set of edges M of a graph G such that each vertex is incident to exactly two edges of M. Thus M determines a set of cycles in G.

One can efficiently compute minimum cost 2-factors in weighted graphs. It is open whether one can do the same, if we forbid triangles, i.e., each cycle has at least four edges. For the unweighted case, a complicated result of Hartvigsen shows that one can find such a 2-matching in polynomial time.

In the talk, we will review known results related to finding triangle free 2-factors, see its relation to the traveling salesman problem, and discuss several open problems.

**2019-10-04:**

**Author: ** Renaud Chicoisne, HEC Montreal.

**Where:** Av República 701, Sala 33.

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

**Title:** Set-based Lagrangean decomposition methods for mathematical programming

**Abstract:** We present generic Lagrangean frameworks for primal (variable) and dual (constraint) decomposition algorithms for nonlinear mathematical programs with generalized inequalities.

Akin to the Dantzig-Wolfe (DW) method and the Benders Decomposition (BD), we solve a succession of restricted problems/Lagrangean relaxations in a primal setting or relaxed problems/second stage problems in a dual standpoint.

Our approach is generic in the sense that it takes as user-defined inputs

1) a structured subset of the primal (dual) feasibility set, and

2) a mechanism to update it at each iteration.

Depending on the type of subset, the master problems (primal restricted or dual relaxed problem) can have very different structures and properties.

We discuss how the structures of the set and the update mechanism influence the number of iterations required to obtain an optimal or near-optimal solution and the difficulty to solve the master problems. Our meta-algorithm presents a new generic way to prove convergence of – among others – the special cases of DW, BD and recent works arising from an 2009 article of Bienstock and Zuckerberg. We also present linearized schemes to alleviate the computational burden of solving the Lagrangean relaxation in a primal setting or the relaxed problem in a dual setting.

**2019-20-03:**

**Author: ** Mathieu Mari, École Normale Supérieure .

**Where:** Av República 701, Sala 33.

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

**Title:** Maximizing Covered Area in a Euclidean Plane with Connectivity Constraint

**Abstract:** Given a set of unit disks in the plane and an integer K, the maximum area connected subset problem asks for a subset of K disks covering the maximum area, under the constraint that the area covered by the K disks is connected. This problem is motivated by wireless router deployment and is a special case of maximizing a submodular function under a connectivity constraint.

We prove that the problem is NP-hard and analyze a greedy algorithm, proving that it is a 1/2-approximation. We then give a polynomial-time approximation scheme (PTAS) for this problem with resource augmentation, i.e., allowing an additional set of epsilon*K disks that are not drawn from the input. Additionally, for two special cases of the problem, we design a PTAS without resource augmentation.

**2019-13-03:**

**Author: ** Rodrigo Botelho Ribeiro, Universidad Católica de Chile.

**Where:** Av República 701, Sala 33.

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

**Title:** Preferential Attachment Random graphs with edge-step functions

**Abstract:** Nowadays, modeling and understanding the evolution and properties of concrete networks are important questions for many areas in the scientific community. The huge amount of data generated these days combined with new computing power allowed us to see concretely how many entities, such as our own society, are organized and connected. These findings naturally motivated the investigation of many models that intended to reproduce the properties observed empirically.

In this seminar, in its first moment, we will introduce which kind of properties one desires to see on a random graph (network) model and why. Then, we will discuss some recent results on a generalization of the traditional Barabasi-Albert model whose parameter is a positive function that drives the growth rate of the vertex set. Finally, we discuss nice open questions on this class of models.

**2019-06-03:**

**Author: ** Suraj Malladi, Standford U.

**Where:** Sala i34 (3rd floor, República 799B).

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

**Title:** Fair Auctions with Asymmetrically Informed Bidders

**Abstract:** (With Aranyak Mehta and Uri Nadav) Agents often arrive to auctions with different levels of informations about their own value for the object sold. In such asymmetric settings, it may be optimal to charge different reservation prices to discriminate between bidders. However, it is often infeasible to expressly treat different bidders in the same auction differently, particularly in on-line settings. We characterize optimal nondiscriminatory mechanisms in the presence of informational asymmetries and compares them to the revenue of unconstrained optimal auctions. We find the revenue of the unconstrained optimal auctions never exceeds between twice to four-thirds of the optimal nondiscriminatory auction’s revenue.

**2018-26-12:**

**Author: ** Matias Siebert, Georgia Tech.

**Where:** Republica 701, Sala 33.

**When:** Wednesday, December 26, 14:30.

**Title:** A Linear Programming Based Approach to the Steiner Tree Problem with a Fixed Number of Terminals

**Abstract:** We present a set of integer programs (IPs) for the Steiner tree problem with the property that the best solution obtained by solving all, provides an optimal Steiner tree. Each IP is polynomial in the size of the underlying graph and our main result is that the linear programming (LP) relaxation of each IP is integral so that it can be solved as a linear program. However, the number of IPs grows exponentially with the number of terminals in the Steiner tree. As a consequence, we are able to solve the Steiner tree problem by solving a polynomial number of LPs, when the number of terminals is fixed.

**2018-28-11:**

**Author: ** Raimundo Saona, DIM, U Chile.

**Where:** Republica 701, Sala 33.

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

**Title:** Prophet Secretary Through Blind Strategies

**Abstract:** In the classic prophet inequality, a problem in optimal stopping theory, samples from independent random variables arrive online. A gambler that knows the distributions, but cannot see the future, must decide at each point in time whether to stop and pick the current sample or to continue and lose that sample forever. The goal of the gambler is to maximize the expected value of what she picks and the performance measure is the worst case ratio between the expected value the gambler gets and what a prophet, that sees all the realizations in advance, gets. We study when the samples arrive in a uniformly random order, deriving a way of analyzing multi-threshold strategies that basically sets a nonincreasing sequence of thresholds to be applied at different times. The gambler will thus stop the first time a sample surpasses the corresponding threshold. We consider a class of robust strategies that we call blind quantile strategies. These constitute a clever generalization of single threshold strategies. Our main result shows that these strategies can achieve a constant of 0.669 in the prophet secretary problem, done by a sharp analysis of the underlying stopping time distribution for the gambler’s strategy that is inspired by the theory of Schur-convex functions. We further prove that our family of blind strategies cannot lead to a constant better that 0.675. Finally we prove that no nonadaptive algorithm for the gambler can achieve a constant better than 0.732.

**2018-14-11:**

**Author: ** Nishant Mehta, University of Victoria.

**Where:** Republica 701, Sala 33.

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

**Title:** Fast Rates for Unbounded Losses: from ERM to Generalized Bayes

**Abstract:** I will present new excess risk bounds for randomized and deterministic estimators, discarding boundedness assumptions to handle general unbounded loss functions like log loss and squared loss under heavy tails. These bounds have a PAC-Bayesian flavor in both derivation and form, and their expression in terms of the information complexity forms a natural connection to generalized Bayesian estimators. The bounds hold with high probability and a fast $\tilde{O}(1/n)$ rate in parametric settings, under the recently introduced central’ condition (or various weakenings of this condition with consequently weaker results) and a type of ‘empirical witness of badness’ condition. The former conditions are related to the Tsybakov margin condition in classification and the Bernstein condition for bounded losses, and they help control the lower tail of the excess loss. The ‘witness’ condition is new and suitably controls the upper tail of the excess loss. These conditions and our techniques revolve tightly around a pivotal concept, the generalized reversed information projection, which generalizes the reversed information projection of Li and Barron. Along the way, we connect excess risk (a KL divergence in our language) to a generalized Rényi divergence, generalizing previous results connecting Hellinger distance to KL divergence.

This is joint work with Peter Grünwald.

**2018-07-11:**

**Author: ** Mircea Petrache, Facultad de Matemáticas, PUC.

**Where:** Republica 701, Sala 33.

**When:** Wednesday, November 07, 14:30.

**Title:** Isoperimetric inequality on some periodic graphs, and the shape of

optimal point clusters

**Abstract:** I will start by presenting a proof of some general isoperimetric inequalities in euclidean space by Trudinger (in the new version by Cabre’), via a simple PDE-based strategy. The goal of the talk is to show that the same idea can sometimes be transferred to get isoperimetric inequalities on simple graphs (of which the only published one is for the d-dimensional grid Z^d, by Hamamuki). After presenting these two proofs, I’ll discuss ways in which these can be extended to more general classes of periodic graphs, allowing some interesting transfer of information from PDE ideas to combinatorics problems.

**2018-08-10:**

**Author: ** Cristóbal Guzmán, Instituto de Ingeniería Matemática y Computacional, PUC.

**Where:** Republica 701, Sala 33.

**When:** Wednesday, October 10, 14:30.

**Title:** The power of parallelization in large-scale convex optimization

**Abstract:** Recently there has been an outburst of parallelization techniques to speed up optimization algorithms, particularly in applications in statistical learning and structured linear programs. Motivated by these developments, we seek for theoretical explanations of provable improvements (or the lack thereof) in performance obtained by parallelizing optimization algorithms. In 1994, Nemirovski proved that for low-dimensional optimization problems there is a very limited improvement that could be obtained by parallelization, and furthermore conjectured that no acceleration should be achievable by these means. In this talk, I will present new results showing that in high-dimensional settings no acceleration can be obtained by parallelization, providing strong evidence towards Nemirovski’s conjecture.

Based on ongoing work with Jelena Diakonikolas (UC Berkeley) and Adam Smith (Boston U).

**2018-26-09:**

**Author: ** Maria Saumell, Czech Academy of Sciences, Czech Republic.

**Where:** Republica 701, Sala 33.

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

**Title:** A Median-Type Condition for Graph Tiling

**Abstract:** Komlos determined the asymptotically optimal minimum degree condition for covering a given proportion of vertices of a host graph by vertex-disjoint copies of a fixed graph H. We show that the minimum degree condition can be relaxed in the sense that we require only a given fraction of vertices to have the prescribed degree. Joint work with Diana Piguet.

**2018-12-09:**

**Author: ** Hans Raj Tiwary, Charles U, Czech Republic.

**Where:** Republica 701, Sala 33.

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

**Title:** Extension Complexity

**Abstract:** A polytope Q is called an extension of a polytope P if P is a projection of Q. The extension complexity of a polytope is the minimum number of inequalities needed to describe any of its extensions. In this talk I will describe some results related to extension complexities of several important polytopes arising in combinatorial optimization and discuss how extension complexity can be used to model computational difficulty of solving problems.

**2018-05-09:**

**Author: ** Abner Turkieltaub, U Chile.

**Where:** Republica 701, Sala 33.

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

**Title:** Strong Algorithms for the Ordinal Matroid Secretary Problem.

**Abstract:** A general technique and analysis for the matroid secretary problem is presented and then we show how to achieve a 4-competitive algorithm for the case

of graphic matroids.

**2018-29-08:**

**Author: ** Andreas Wiese, U Chile.

**Where:** Republica 701, Sala 33.

**When:** Wednesday, August 29, 13:30.

**Title:** A (5/3 + ε)-Approximation for Unsplittable Flow on a Path: Placing Small Tasks into Boxes

**Abstract:** In the unsplittable flow on a path problem (UFP) we are given a path with edge capacities and a collection of tasks. Each task is characterized by a subpath, a profit, and a demand. Our goal is to compute a maximum profit subset of tasks such that, for each edge e, the total demand of selected tasks that use e does not exceed the capacity of e.

The current best polynomial-time approximation factor for this problem is 2 + eps for any constant eps>0. This is the best known factor even in the case of uniform edge capacities. These results, likewise most prior work, are based on a partition of tasks into large and small depending on their ratio of demand to capacity over their respective edges: these algorithms invoke (1 + eps)-approximations for large and small tasks separately. The known techniques do not seem to be able to combine a big fraction of large and small tasks together (apart from some special cases and quasi-polynomial-time algorithms).

The main contribution of this paper is to overcome this critical barrier. Namely, we present a polynomial-time algorithm that obtains roughly all profit from the optimal large tasks plus one third of the profit from the optimal small tasks. In combination with known results, this implies a polynomial-time (5/3 + eps)-approximation algorithm for UFP.

Joint work with Fabrizio Grandoni, Tobias Mömke and Hang Zhou.

**2018-21-08:**

**Author: ** Claudio Telha, U Andes.

**Where:** Republica 701, Sala 33.

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

**Title:** A sequential variant of the inspection game.

**Abstract:** An inspection game models the problematic of an inspector who must verify

that one or more operators adhere to certain regulations. Inspectees have a potential interest to violate these regulations but they get punished if they are caught violating them. It is costly for the inspector to verify that every operator is complying with the regulations. Thus, he performs a limited number of inspections in order to deter operators from acting illegally.

Suppose the regulation amounts to perform certain instantaneous task. We present some preliminary results on a sequential inspection game where operators agree to immediately reveal if they are inspected. The inspector sequentially visits k out of n operators, and each of them uses the partial information on the inspection path to dynamically decide if and when to perform the required task. The presentation focuses on the description of the model and how to find an equilibrium in the case k=2.

**2018-08-08:**

**Author: ** Bruno Karelovic, Paris 7.

**Where:** Republica 701, Sala 33.

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

**Title:** Concurrent stochastic priority games

**Abstract:** Concurrent stochastic games are a special class of zero-sum two-players game where at each state both players choose simultaneously and independently the actions to execute, and the probabilistic transition depends on both actions selected by the players.

We examine the class of priority games. The priority games constitute a natural extension of parity games, this latter class is the class of games popular in computer science having applications in automata theory and verification.

The main result of this chapter is that the values of the concurrent stochastic priority games can be obtained as a nested nearest fixed point of appropriate monotone nonexpansive mapping.

**2018-01-08:**

**Author: ** Christopher Thraves, U Concepción.

**Where:** Republica 701, Sala 33.

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

**Title:** Sitting closer to friends than enemies, revisited.

**Abstract:** The Sitting Closer to Friends than Enemies problem is to find an embedding in a metric space for the vertices of a given signed graph so that, for every pair of incident edges with different sign, the positive edge has to be shorter (in the metric of the space) than the negative edge. In this talk, I will give a gentle introduction and will present a collection of results regarding this problem. In particular, I will show a characterization for the sets of signed graphs for which there exist such an embedding in \mathbb{R}, in the circle, and in trees. Moreover, I will show an upper and lower bound on the number of vertices of a signed graph such that there exists such an embedding in \mathbb{R}^n. Finally, I will present interesting questions that are still open about this problem.

**2018-20-06:**

**Author: ** Victor Verdugo, U O’Higgins.

**Where:** Republica 701, Sala 33.

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

**Title:** About a problem on real time scheduling and control

**Abstract:** Certain control computations require to be co-scheduled, each of which is allowed to be skipped occasionally. This may be modeled as periodic tasks with the correctness requirement that for each one, the fraction of jobs that complete execution should be at least some specified value between zero and one. I will show you two different real time scheduling models to formalize the problem, and derive approximation algorithms. Time permitting, I would also like to discuss about the model and solution strategies, and what other variants can be consider in order to capture different control environments. (Joint work with A. Marchetti-Spaccamela, V. Bonifaci and S. Baruah).

**2018-06-06:**

**Author: ** Andrés Cristi, U Chile.

**Where:** Republica 701, Sala 33.

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

**Title:** Negative Prices in Stackelberg Network Pricing Games

**Abstract:** A Stackelberg network pricing game is a two-stage game, in which, in the first stage, a leader sets prices/tolls for a 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 sink. Labbé et al. (1998) showed that finding optimal prices with lower bounds is NP-hard and gave an example in which profit is maximized by using negative prices. We explore this last phenomena and study the following two questions already posted in an open problem session of the AGCO Seminar. First, for which network topologies can the leader increase profit by using negative prices? Second, how much more profit can the leader realize by setting negative prices? During this talk we will answer these two questions for the single follower setting and partly for the multiple followers setting. If time permits we will also discuss the problem in a more general strategy space for the follower.

This is joint work with Marc Schröder.

**2018-16-05:**

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

**Where:** Republica 701, Sala 33.

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

**Title:** On the equitable Hamiltonian Cycle problem

**Abstract:** Kinable, Smeulders, Delcour, and Spieksma (2017) introduced the Equitable TSP (E-TSP). In the E-TSP, we are given an even number of cities and distances between each pair of these. Instead of finding a tour of minimum length, Kinable et al. (uniquely) decomposed the tour in two perfect matchings, one with “even” edges and one with “odd” edges and the goal is to minimize the difference between the costs of the two perfect matchings. Kinable et al. show that the E-TSP is strongly NP-hard by reduction from Hamiltonian Cycle. The reduction resembles the reduction to show that TSP is strongly NP-hard. In the reduction for TSP, it suffices to set each distance to one of two values, e.g., 0 or 1. The reduction used for the E-TSP, however, needs to have many different values for the distances. This raises the question whether the optimal solution-value to the E-TSP when each distance can only be one of two values needs to be 0 or is positive.

We generalized this question to the Equitable Hamiltionian Cycle Problem: given a complete graph on an even number of vertices in which each edge is either red or blue, can we find a tour on all vertices such that the “even” perfect matching has as many red edges as the “odd” perfect matching. We will show that the answer to this question is NO and YES, and for the YES-case we present the idea on how to find such a tour in O(n log n) or even O(n) time. Furthermore, if time permits, we also discuss how well some simple local search algorithm will perform.

This is joint work with Frits Spieksma and Tim Ophelders (TU Eindhoven)

**2018-09-05:**

**Author: ** Jeremy Barbay, DCC, U Chile.

**Where:** Republica 701, Sala 33.

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

**Title:** Adaptive Computation of Frechet Distance: Upper and Conditional Lower Bound

**Abstract:** The Fréchet distance is a measure of similarity between curves that takes into account the location and ordering of the points along the curves, and permits to abstract, among other things, differences of resolution between the two curves (with application to morphing, handwriting recognition and protein structure alignment, among others).

In 1991, Art and Godau introdued this measure to Computational Geometry, describing an algorithm computing the Fréchet distance between two polygonal curves composed of $n$ and $m$ segments respectively in time within $O(mn\log(mn))$, the first algorithm to do so in polynomial time. In 1994, Eiter and Mannila extended the notion of the Fréchet distance between curves to the Fréchet distance between sequence of points of respective sizes $n$ and $m$, demonstrating that the latter cam be computed in time within $O(nm)$ and space within $O(n+m)$, and that it gives a good approximation of the Fréchet distance.

After 20 years without major improvements and no better lower bound than $\Omega(n+m)$, Bringmann decribed in 2014 the first conditional lower bound for the computation of the Discrete Fréchet Distance, via a clever reduction to CNF-SAT, under the Strong Exponential Time Hypothesis (SETH), which yield in turn many similar results for other problems using similar dynamic programming techniques (e.g. DIR Edit Distance).

We propose a refinement of the algorithm and the analysis from Eiter and Mannila to take into account not only the sizes $n$ and $m$ of the point sequences, but also of the difficulty $\omega$ to certify the resulting distance, and the corresponding refinement of the conditional lower bound from Bringmann to take into account this new parameter. It is our hope that such a refinement of the analysis can be (easily?) extended to other problems for which dynamic programming has given good results in the past.

**2018-02-05:**

**Author: ** Jan Corsten, The London School of Economics.

**Where:** Republica 701, Sala 33.

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

**Title:** Tiling edge-coloured complete graphs with few monochromatic graphs of bounded degree

**Abstract:** Erdős, Gyárfás and Pyber proved in 1991 that the vertices of every $r$-edge-coloured complete graph on $n$ vertices can be partitioned into $O(r^2 log r)$ monochromatic cycles. It is very interesting and maybe surprising that this bound is independent of $n$. Grinshpun and Sárközy showed that in the case of two colours, a similar conclusion is true not only for cycles but any family of graphs of bounded degree. In this talk, we consider the same problem for multiple colours.

**2018-25-04:**

**Author: ** Andreas Toennis, U Chile & MPII.

**Where:** Republica 701, Sala 33.

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

**Title:** Lower Bounds for Online Matching on the Line.

**Abstract:** In the online matching on the line problem, the task is to match a set of requests R online to a given set of servers S. The distance metric between any two points in R ∪ S is a line metric and the objective for the online algorithm is to minimize the sum of distances between matched server-request pairs. This problem is well-studied and – despite recent improvements – there is still a large gap between the best known lower and upper bounds: The best known deterministic algorithm for the problem is O(log^2(n))-competitive, while the best known deterministic lower bound is 9 .001. The lower and upper bounds for randomized algorithms are 4.5 and O(log n) respectively.

We prove that any deterministic online algorithm which in each round: ( i) bases the matching decision only on information local to the current request, and (ii) is symmetric (in the sense that the decision corresponding to the mirror image of some instance I is the mirror image of the decision corresponding to instance I), must be Ω(log n)-competitive. We then extend the result by showing that it also holds when relaxing the symmetry property so that the algorithm might prefer one side over the other, but only up to some degree. This proves a barrier of Ω(log n) on the competitive ratio for a large class of “natural” algorithms. This class includes all deterministic online algorithms found in the literature so far.

Furthermore, we show that our result can be extended to randomized algorithms that locally induce a symmetric distribution over the chosen servers. The Ω(log n)-barrier on the competitive ratio holds for this class of algorithms as well.

**2018-16-04:**

**Author: ** Neil Olver, VU University Amsterdan and CWI.

**Where:** Republica 701, Sala 33.

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

**Title:** The long-term behaviour of a queue-based dynamic traffic model.

**Abstract:** The fluid queueing model, introduced by Vickrey in ’69, is probably the simplest model that plausibly captures the notion of time-varying flows. Although the model is quite simple, our current theoretical understanding of equilibrium behaviour in this model is rather limited, and many fundamental questions remain open. I will discuss the resolution of a deceptively simple-sounding problem: do queue lengths remain bounded in the equilibria under natural necessary conditions? (Joint work with Roberto Cominetti and José Correa).

**2018-11-04:**

**Author: ** J. Correa, U Chile.

**Where:** Republica 701, Sala 33.

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

**Title:** An open problem on matchings.

**2018-04-04:**

**Author: ** Fábio Botler, Andrés Cristi, Andreas Tönnis, and Kevin Schewior, U Chile.

**Where:** Republica 701, Sala 33.

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

**Title:** SUPERSET: A (super)natural variant of the card game SET.

**Abstract:** We consider SUPERSET, a lesser-known but interesting variant of the famous card game SET. Here, players look for SUPERSETs instead of SETs, that is, the symmetric difference of two SETs that intersect in exactly one card. In this paper, we pose questions that have been previously posed for SET and provide answers to them; we also show relations between SET and SUPERSET.

For the regular deck of cards, which can be identified with F_3^4, we give an elegant proof for the fact that the maximum number of cards that can be on the table without having a SUPERSET is 9, solving an open question (McMahon et al., 2016). For the deck corresponding to F_3^d, we show that this number is Omega(1.442^d) and O(1.733^d). We also compute probabilities of the presence of a superset in a collection of cards drawn uniformly at random. Finally, we consider the computational complexity of deciding wether a multi-value version of SET or SUPERSET is contained in a given set of cards, and show an FPT-reduction from the problem for SET to that for SUPERSET, implying W[1]-hardness of the problem for SUPERSET.

This is joint work with Ruben Hoeksma.

**2018-28-03:**

**Author: ** Yossi Arjevani, Weizmann Institute of Science.

**Where:** Republica 701, Sala 33.

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

**Title:** Structural-based Approach to Complexity of Optimization Algorithms.

**Abstract:**The past few decades have witnessed tremendous progress in the field of Mathematical Optimization which led to a large proliferation of new optimization methods to many scientific fields. Among these is the field of machine learning whose applicability heavily relies on solvers which are capable of efficiently solving challenging large-scale optimization problems. Notwithstanding, we still lack an adequate complexity theory which satisfactorily quantifies the computational resources required for solving optimization problems of this nature. Motivated by the limitations of current computational models, in the present work we propose novel theoretical foundations for investigating the computational boundaries of optimization algorithms which scale well with the dimension of the problem. We then present recent results regarding application of this technique on various types of optimization problems.

**2018-21-03:**

**Author: ** Tim Oosterwijk, U Chile.

**Where:** Republica 701, Sala 33.

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

**Title:** Approximating Vector Scheduling

**Abstract:** In this talk we will consider the Vector Scheduling problem, a natural generalization of the classical makespan minimization problem to multiple resources. Here, we are given n jobs, represented as d-dimensional vectors in [0,1]^d, and m identical machines, and the goal is to assign the jobs to machines such that the maximum load of each machine over all the coordinates is at most 1. For fixed d, the problem admits an approximation scheme, and the best known running time is n^{f(epsilon,d)}, where f(epsilon,d) = (1/epsilon)^{Õ(d)}, where Õ suppresses polylogarithmic terms in d. In particular, the dependence on d is double exponential. In this talk we will show that a double exponential dependence on d is necessary, and give an improved algorithm with essentially optimal running time. This gives the first efficient approximation scheme (EPTAS) for the problem. This is joint work with Nikhil Bansal, Tjark Vredeveld and Ruben van der Zwaan.

**2018-14-03:**

**Author: ** Bruno Ziliotto.

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

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

**Title:** Markov Decision Processes with long duration

**Abstract:** In a Markov Decision Process (MDP), at each stage, knowing the current state, the decision-maker chooses an action, and receives a reward depending on the current state of the world. Then a new state is randomly drawn from a distribution depending on the action and on the past state. Many optimal payoffs concepts have been introduced to analyze the strategic aspects of MDPs with long duration: asymptotic value, uniform value, liminf average payoff criterion… We provide sufficient conditions under which these concepts coincide, and discuss some open problems. (Joint work with Xavier Venel, Paris 1 University).

**2018-05-01:**

**Author: ** Kurt Mehlhorn, MPII.

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

**When:** **Friday, January 05, 12:00.**

**Title:** Markets and Fair Division of Goods.

**Abstract:** Items have to be distributed to agents in a fair manner. The agents have valuations for the goods and the value of a set of goods is simply the sum of the valuations. Nash introduced axioms for fairness and showed that for divisible goods maximizing the product of the agent’s valuations leads to a fair division. The allocation maximizing the product is the same as the allocation in a Fisher market in which all agents have the same budget. For indivisible goods the problem is harder. Cole/Gkatzelis gave an approximation algorithm based on rounding the allocation in a Fisher market with earning caps. We go further and consider Fisher markets with earning and utility caps, i.e., buyers do not want to buy goods beyond a certain utility and sellers do not want to earn money above a certain amount. We show how to computer approximate equilibria in such markets and how this leads to fair divisions for buyers with utility caps. The talk is based on papers in SODA ’18, SAGT ’17, ESA ’16, and SODA ’16.

**2018-05-01:**

**Author: ** Alfredo Torrico, GaTech.

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

**When:** **Wednesday, January 03, 14:00.**

**Title:** Robust Submodular Maximization: Offline and Online algorithms.

**Abstract:** In this work, we consider the robust submodular maximization problem subject to a matroid constraint in the offline and online setting. In the offline version, we are given a collection of k monotone submodular functions and matroid on a ground set of size n. The goal is to select one independent set that maximizes the minimum of the submodular functions. Given the complexity of the problem, we design a bi-criteria approximation algorithm that returns a set that is the union of a logarithmic number of independent sets. In the online version of the problem, we receive a new collection of functions at each time step and aim to pick an independent set in every stage. We measure the performance of the algorithm in the expected regret setting. Again, we present a bi-criteria approximation algorithm which gives a (nearly) optimal approximation as well as regret bounds. Our result rely crucially on modifying the Follow-the-Perturbed-Leader algorithm of Kalai and Vempala.

**2017-27-12:**

**Author: ** Nicolás Sanhueza, University of Birmingham.

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

**When:** Wednesday, December 27, 14:30.

**Title:** An asymptotic bound for the strong chromatic number.

**Abstract:** The strong chromatic number of a graph G on n vertices is the least number r with the following property: after adding isolated vertices to G so that the number of vertices is divisible by r, and taking the union with any collection of spanning disjoint copies of K_r in the same vertex set; the resulting graph has a proper vertex-colouring with r colours.

We show that for every c>0 and every graph G on n vertices with maximum degree Δ(G)≥cn, the strong chromatic number is at most (2+o(1))Δ(G), which is asymptotically best possible.

**2017-20-12:**

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

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

**When:** Wednesday, December 20, 14:30.

**Title:** The Itinerant List-Update Problem

**Abstract:** We introduce the Itinerant List-Update Problem (ILU), which is a relaxation of the classic List-Update Problem (LU) in which the pointer no longer has to return to a home location after each request. The motivation to introduce ILU arises from the application of track management in Domain Wall Memory. We first show an Omega(log n) lower bound on the competitive ratio for any randomized online algorithm for ILU. This shows that online ILU is harder than online LU, for which O(1)-competitive algorithms, like Move-To-Front, are known. We then show that ILU is essentially equivalent to a variation of the Minimum Linear Arrangement Problem (MLA), which we call the Dynamic Minimum Linear Arrangement (DMLA) problem. We then give an offline polynomial-time algorithm for DMLA and show that it has an polylogarithmic approximation guarantee.

This is joint work with Neil Olver, Kirk Pruhs, René Sitters, and Leen Stougie.

**2017-13-12:**

**Author: ** Bhalchandra D. Thatte (UFMG, Brazil)

**Where:** Republica 779B, **Sala P2, 2nd floor**.

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

**Title:** Subgraph posets and graph reconstruction.

**Abstract:** In the 1940s, Ulam and Kelly conjectured that a simple undirected finite graph on at least 3 vertices can be reconstructed (up to isomorphism) from the collection of its unlabelled vertex-deleted subgraphs. In this talk I will give an introduction to the problem and some of its variations. I will then discuss some of my work on the problem of reconstructing graphs from certain partially ordered sets of subgraphs, and its relation to the reconstruction problem of Ulam and Kelly.

**2017-06-12:**

**Author: ** Andreas Tönnis, U Chile.

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

**When:** Wednesday, December 6, 14:30.

**Title:** The Temp Secretary Problem and Extensions.

**Abstract:** The Temp Secretary Problem was recently introduced by Fiat et al. It is

a generalization of the Secretary Problem, in which commitments are temporary for a fixed duration. This problem is closely related to online interval scheduling with random arrival dates and other online “on-the-line” problems. We present a simple online algorithm with improved performance guarantees for unit-sized items with uniform arrival rates. Our algorithmic approach uses a non-temporal relaxation. This allows us to bound the collected expected value by known techniques for the random-order model. We discuss algorithmic ideas, basic proof techniques and extensions to open problems like non-uniform arrival rates, non-uniform capacities and covering variants. This talk is based on joined work with Thomas Kesselheim.

**2017-22-11:**

**Author: ** Johannes Fischer, TU Dortmund.

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

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

**Title:** Simple, Fast and Lightweight Parallel Wavelet Tree Construction.

**Abstract:** The wavelet tree (Grossi et al. 2003) and wavelet matrix (Claude et al. 2015) are compact indices for texts over an alphabet [0,\sigma) that support rank, select and access queries in O(log \sigma) time. We first present new practical sequential and parallel algorithms for wavelet tree construction. Their unifying characteristics is that they construct the wavelet tree bottom-up, i.e., they compute the last level first. We also show that this bottom-up construction can easily be adapted to wavelet matrices. In practice, our best sequential algorithm is up to twice as fast as the currently fastest sequential wavelet tree construction algorithm (serialWT), simultaneously saving a factor of 2 in space. This scales up to 32 cores, where we are about equally fast as recWT (the currently fastest parallel wavelet tree construction algorithm), but still use only about 75% of the space.

**2017-15-11:**

**Author: ** Claudio Telha Cornejo, CORE & OM Partners.

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

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

**Title:** A competitive uncapacitated lot-sizing game.

**Abstract:** We study a game merging the lot-sizing problem with a Cournot competition. Each player is a producer with her own production facility, modeled as an uncapacitated lot-sizing problem (i.e., production incurs set-up and variable costs and inventories are allowed). A Cournot competition is played in each time period (market) with each player deciding the quantity of product to place on it. The market price of that product in each time period depends on the total quantity placed in the market.

In this talk we discuss some algorithmic results regarding the complexity of finding a Nash equilibrium for this game. It is based on joint work with Margarida Carvalho, João Pedro Pedroso and Mathieu Van Vyve.

**2017-08-11:**%0