AGCO Seminar

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-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-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:

Author: Daniel Quiroz, U Chile.

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

When: Wednesday, November 8, 14:30.

Title: Colouring with conditions on distances

Abstract:
A natural generalisation of the chromatic number comes from requiring vertices to have a different colour if they have distance at most p. In this context, it is clear that upper bounds on the number of colours depend on the maximum degree of the graph. A lot of work has been done on this topic, in particular around Wegner’s conjecture for planar graphs and distance 2. The situation changes if we require vertices to have a different colour if they have distance exactly p. For that type of colouring, the answer to the question “how many colours are needed?”, depends greatly on the parity of p. In the talk I will give an overview of the work that has been done on these types of colouring, and will discuss in more detail our new results on colouring at distance exactly p. The talk is based on joint work with Jan van den Heuvel and H.A. Kierstead.

2017-11-10:

Author: Andrés Cristi, U Chile.

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

When: Wednesday, October 11, 14:30.

Title: A Near Optimal Mechanism for Energy Aware Scheduling

Abstract:
Consider a cloud server, where clients can submit jobs for processing. The quality of service that each agent receives is given by a private non-decreasing function of the completion time of her job. The server has to process the jobs and charge each agent while trying to optimize the social cost that is defined as the energy expenditure plus the sum of the values of the internal cost functions. The server operator would like to design a mechanism in order to optimize this objective, which ideally is computationally tractable, charges the users “fairly” and the induced game has an equilibrium. We present a mechanism that combines the aforementioned properties with a constant Price of Anarchy. An interesting feature of our mechanism is that it is indirect: each user needs only to declare an upper bound on the completion time of her job, and not the cost function.

2017-04-10:

Author: José Verschae, PUC.

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

When: Wednesday, October 02, 14:30.

Title: Symmetry and hierarchies in approximation algorithms: some open problems

Abstract:
One of the most important tools for obtaining good approximation algorithms is based on linear and semi-definite relaxations. Different “hierarchies” have appeared in the literature that try to automatically yield best possible polynomial-size relaxations. Recently, many examples have appeared showing that these techniques perform poorly in the presence of symmetries. In this talk I will first present some general techniques for dealing with symmetries based on computational group theory. Then I will introduce the basics of the Sherali-Adams hierarchy and state some open problems that need to be addressed in order to apply group theoretical techniques in the context of the Sherali-Adams hierarchy.

2017-27-09:

Author: Martin Matamala, DIM, U Chile.

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

When: Wednesday, September 27, 14:30.

Title: An extension of (perfect) matching

Abstract:
Consider a finite graph where each vertex v is colored with a color c(v).
The new structure, call it X-(perfect) matching, is an edge coloring
(not necessarily proper) s.t. each vertex v has at most (exactly)
one incident edge colored with color c(v).
When all vertices have the same color, then a X-(perfect) matching is
a (perfect) matching of the graph.

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