# AGCO Seminar

### The ACGO seminars are held online every wednesday as part of an effort of a group of researchers around the topics of Algorithms, Combinatorics, Game Theory and Optimization in Chile. Starting March 2022, the seminar takes place fully in face-to-face mode. The usual date for the seminar is on Wednesday at 3pm.

### 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.

Abril

### Nov 29 - 2023

Speaker: Tomasz Steifer, PUC.

Title: Online learning with consistency oracle

When: Nov 19, 3:00pm.

Where: Sala de Seminario von Neuman, CMM, Beauchef 851, torre norte.

Abstract:

A binary classification game is being played between a learner and an adversary. At each round, the adversary selects a natural number x and the learner has to predict its label h(x). Is there a bound on the number of mistakes made by the learner, assuming that h comes from some class H? Littlestone gave a learning algorithm which achieves an optimal mistake bound d, provided H has a certain combinatorial property. However, Littlestone's algorithm is believed to be computationally demanding. Can we have a feasible strategy for the learner and if so, how many mistakes would it make? I will introduce such a strategy, which is fast (for finite classes) and achieves an exponential (in d) mistake bound. The algorithm was devised together with Sasha Kozachinskiy.

### Nov 15 - 2023

Speaker: Felipe Subiabre, DII, U Chile.

Title: Optimal Disease Screening Policies Under Budget Constraints

When: Nov 15, 3:00pm.

Where: Sala Multimedia, 6to piso, CMM, Beauchef 851, torre norte.

Abstract:

We study the problem of selecting screening policies for a given disease in a large population which is divided into risk groups, and where we have a measure of benefit and cost for each possible policy. We want to find a selection of them, one for each risk group so that the total benefit is maximized and a budget constraint per time period is satisfied.

To that end we start from an individual base model that accounts for the probabilistic appearance and evolution of the disease along stages. Our main result is an ergodic-like theorem which allows us to calculate the expected costs and benefits for each policy. This result is applicable to a rich class of individual models (discrete and continuous-time semi-Markov processes) currently used in the literature.

The presentation is grounded in the application to cancer screening, but can be extended to other non-contagious diseases. We wil show examples of some individual models and how our methodology allows for the efficient evaluation and optimization of large families of policies. If time permits we will also discuss the relation between our methodology and some other approaches (Markov decision processes, flowgraph models), and some future work.

### Nov 08 - 2023

Speaker: Maximilian Fichtl, DII, U Chile

Title: Computing Bayes-Nash Equilibria in Auctions via Online Learning

When: Nov 08, 3:00pm.

Where: Sala de Seminario von Neuman, CMM, Beauchef 851, torre norte.

Abstract:

Auction games are a central application of game theory in economics. However, while explicit formulas for Bayes-Nash equilibria are known for particular auction settings, we generally have to rely on numerical methods to predict the outcomes of auctions. We present a simple class of learning algorithms to approximate Bayes-Nash equilibria in these games. Surprisingly, while recent theoretical results suggest that such algorithms perform poorly in general matrix games, we provide experimental evidence that they perform very well in many different auction scenarios.

Despite the positive experimental results, proving the convergence of these algorithms remains an open problem - even in very basic settings. We provide some insights and known preliminary results towards answering this question.

### October 25 - 2023

Speaker: Alba Olivares Nadal, UNSW Business School

Title: Optimal Patient Selection into Care Management Programs

When: October 25, 3:00pm.

Where: Sala de Seminario von Neuman, CMM, Beauchef 851, torre norte.

Abstract:

Care Management Programs (CMPs) coordinate the care for patients with complex care needs and older frail adults, who usually represent the top of healthcare spending. Although CMPs have appeared as credible avenues for reducing healthcare utilization, empirical evidence showed mixed results. Using patient-level data we evaluate the causal impact of the CMP of a major academic medical center, and we find no impact on five healthcare utilization measures. In the light of these negative results, one wonders how can CMPs be improved. To address this question, we use Markov Decision Processes (MDPs) and Dynamic Programming to model the task of optimally allocating treatment amongst patients while fulfilling some capacity constraints. The complexity of such a problem may be very high because healthcare populations may be large enough that gathering information of the current status of each patient and tracking the evolution of their covariates is untenable. To address this challenge we develop the so-called measurized theory, which allows to model MDPs that optimize the distribution of treated and untreated patients instead of dealing with identifed patients. This abstraction transforms a complicated problem into an intuitive formulation and sets the stage for delivering clinically implementable solutions in the future.

### October 11 - 2023

Speaker: Gonzalo Muñoz, Universidad de O'Higgins

Title: Constructing separating hyperplanes for non-convex quadratic problems

When: October 11, 3:00pm.

Where: Sala de Seminario von Neuman, CMM, Beauchef 851, torre norte.

Abstract:

In 1971, Balas introduced the intersection cut framework as a method for generating separating hyperplanes (or "cuts") in integer optimization. These cuts are derived from convex S-free sets, and inclusion-wise maximal S-free sets yield the strongest intersection cuts. When S is a lattice, maximal S-free sets are well-studied from theoretical and computational standpoints. In this talk, we focus on the case when S is defined by a non-convex quadratic inequality and show how to construct basic maximal quadratic-free sets. Additionally, we explore how to generalize the basic procedure to construct a plethora of new maximal quadratic-free sets for homogeneous quadratics. Joint work with Antonia Chmiela, Joseph Paat, and Felipe Serrano.

### October 4 - 2023

Speaker: Jasper van Doornmalen, Eindhoven University.

Title: A Unified Framework for Symmetry Handling

When: October 4, 3:00pm.

Where: Sala de Seminario von Neuman, CMM, Beauchef 851, torre norte.

Abstract:

Discrete optimization problems are often solved using constraint programming or mided-integer programming techniques, using enumeration or branch-and-bound techniques. It is well known that if the problem formulation is very symmetric, there may exist many symmetrically equivalent solutions to the problem. Without handling the symmetries, traditional solving methods have have to check many symmetric parts of the solution space, which comes at a high computational cost.

Handling symmetries in optimization problems is thus essential for devising efficient solution methods. In this presentation, we present a general framework that captures many of the already existing symmetry handling methods. While these methods are mostly discussed independently from each other, our framework allows to apply different symmetry handling methods simultaneously and thus outperform their individual effects. Moreover, most existing symmetry handling methods only apply to binary variables. Our framework allows to easily generalize these methods to general variable types. Numerical experiments confirm that our novel framework is superior to the state-of-the-art methods implemented in the solver SCIP.

### September 27 - 2023

Speaker: Cristian Palma, DIM, U Chile

Title: Load Balancing Algorithms on Scheduling Problems with a Concave Function of the Load

When: September 27, 3:00pm.

Where: Sala de Seminario von Neuman, CMM, Beauchef 851, torre norte.

Abstract:

In load balancing scheduling problems n jobs are to be assigned to m machines. Each job has its own processing time, and we define the load of a machine as the sum of the processing time of all jobs assigned to it.

In this work, the machines have a concave non-decreasing function (accessed through a value oracle) applied to their loads and our goal is to maximize the sum of these valuations.

This setting models a productivity maximization of machines where we aim to allocate indivisible resources, such as fuel tanks.

We prove the existence of a PTAS for the offline version, which is the best possible as the underlying decision problem is strongly NP-hard.

We also explore the online version, where jobs arrive one by one revealing their processing time and must be allocated immediately. We first show that the List Scheduling greedy algorithm is 3/4-competitive in adversarial order. Additionally, we provide an upper bound of ≈ 0.809 (ϕ/2 where ϕ is the golden ratio) for the competitive ratio of any algorithm in this context. For the special case of only two machines, we present an algorithm that matches the given upper bound.

This is joint work with José Soto.

### August 16 - 2023

Speaker: Boris Epstein, GSB, Columbia University

Title: Selection and Ordering Policies for Hiring Pipelines via Linear Programming

When: August 16, 3:00pm.

Where: Sala de Seminario von Neuman, CMM, Beauchef 851, torre norte.

Abstract:

Motivated by hiring pipelines, we study three selection and ordering problems in which applicants for a finite set of positions must be interviewed or made offers to. There is a finite time budget for interviewing or making offers, and a stochastic realization after each decision, leading to computationally-challenging problems. In the first problem, we study sequential interviewing and show that a computationally-tractable, non-adaptive policy that must make offers immediately after interviewing is near-optimal, assuming offerees always accept their offers. In the second problem, we assume that applicants have already been interviewed but only accept offers with some probability; we develop a computationally-tractable policy that makes offers for the different positions in parallel, which can be used even if positions are heterogeneous and is approximately optimal relative to a policy that can make the same amount of offers not in parallel. In the third problem, we introduce a model where the hiring firm is tightly time constrained and must send all offers simultaneously in a single time step, with the possibility of hiring over capacity at a cost; we provide nearly-tight bounds for the performance of practically motivated value-ordered policies. All in all, our paper takes a unified approach to three different hiring problems, based on linear programming. Our results in the first two problems generalize and improve the existing guarantees in the literature that were between 1/8 and 1/2 to new guarantees that are at least 1-1/e ≈ 63.2%.

### August 09 - 2023

Speaker: David Lurie, Paris-Dauphine University (CIFRE)

Title: Weak Ergodicity Approach to POMDPs.

When: August 09, 3:00pm.

Where: Sala de Seminario von Neuman, CMM, Beauchef 851, torre norte.

Abstract:

This seminar introduces Partially Observable Markov Decision Processes (POMDPs), emphasizing their relationship with decision problems and decidability. We then explore a novel theoretical class of POMDPs based on a weak ergodicity property. The seminar concludes by identifying necessary conditions for POMDPs to exhibit this characteristic, bridging the gap between this theoretical result and its potential practical implementation.

### June 28 - 2023

Speaker: Ivan Rapaport, DIM, U Chile

Title: Energy-Efficient Distributed Algorithms for Synchronous Networks

When: June 28, 3:00pm.

Where: Sala de Seminario von Neuman, CMM, Beauchef 851, torre norte.

Abstract:

We study the design of energy-efficient algorithms for well known distributed models of computation: the LOCAL and CONGEST models. Specifically, as a measure of complexity, we consider the maximum, taken over all the edges, or over all the nodes, of the number of rounds at which an edge, or a node, is activein the algorithm. We first show that every Turing-computable problem has a CONGEST algorithm with constant node-activation complexity, and therefore constant edge-activation complexity as well. That is, every node (resp., edge) is active in sending (resp., transmitting) messages for only O(1) rounds during the whole execution of the algorithm. In other words, every Turing-computable problem can be solved by an algorithm consuming the least possible energy. In the LOCAL model, the same holds obviously, but with the additional feature that the algorithm runs in O(poly(n)) rounds in n-node networks. However, we show that insisting on algorithms running in O(poly(n)) rounds in the CONGEST model comes with a severe cost in terms of energy. Namely, there are problems requiring Ω(poly(n)) edge-activations (and thus Ω(poly(n)) node-activations as well) in the CONGEST model whenever solved by algorithms bounded to run in O(poly(n)) rounds. Finally, we demonstrate the existence of a sharp separation between the edge-activation complexity and the node-activation complexity in the CONGEST model, for algorithms bounded to run in O(poly(n)) rounds. Specifically, under this constraint, there is a problem with O(1) edge-activation complexity but Ω(n1/4) node-activation complexity.

(Joint work with Pierre Fraignuiaud, Pedro Montealegre and Ian Todinca)

### June 22 - 2023

Speaker: Paul Gölz

Title: In this apportionment lottery, the House always wins

When: June 22, 3:00pm.

Where: Sala de Seminario von Neuman, CMM, Beauchef 851, torre norte.

Abstract:

Apportionment is the problem of distributing h indivisible seats across states in proportion to the states' populations. In the context of the US House of Representatives, this problem has a rich history and is a prime example of interactions between mathematical analysis and political practice. Grimmett suggested to apportion seats in a randomized way such that each state receives exactly their proportional share qᵢ of seats in expectation (ex ante proportionality) and receives either ⌊qᵢ⌋ or ⌈qᵢ⌉ many seats ex post (quota). However, there is a vast space of randomized apportionment methods satisfying these two axioms, and so we additionally consider prominent axioms from the apportionment literature. Our main result is a randomized method satisfying quota, ex ante proportionality and house monotonicity — a property that prevents paradoxes when the number of seats changes and which we require to hold ex post. This result is based on a generalization of dependent rounding on bipartite graphs, which we call cumulative rounding and which might be of independent interest, as we demonstrate via applications beyond apportionment.

### May 24 - 2023

Speaker: Andrés Cristi, CMM, U Chile

Title: A Constant Factor Prophet Inequality for Online Combinatorial Auctions

When: May 24, 3:00pm.

Where: Sala de Seminario von Neuman, CMM, Beauchef 851, torre norte.

Abstract:

In online combinatorial auctions m indivisible items are to be allocated to n agents who arrive online. Agents have random valuations for the different subsets of items and the goal is to allocate the items on the fly so as to maximize the total value of the assignment. A prophet inequality in this setting refers to the existence of an online algorithm guaranteed to obtain, in expectation, a certain fraction of the expected value obtained by an optimal solution in hindsight. The study of prophet inequalities for online combinatorial auctions has been an intensive area of research in recent years, and constant factor prophet inequalities are known when the agents' valuation functions are submodular or fractionally subadditive. Despite many efforts, for the more general case of subadditive valuations, the best-known prophet inequality has an approximation guarantee of O(log log m).

We prove the existence of a constant factor prophet inequality for the subadditive case, resolving a central open problem in the area.

Our prophet inequality is achieved by a novel, but elementary, sampling idea which we call the Mirror Lemma. This lemma is essentially concerned with understanding algorithms for which the set of items that are allocated and those that are not, distribute equally. The other main ingredient is a nonstandard application of Kakutani's fixed point theorem.

### May 17 - 2023

Speaker: Felipe Valdevenito, DIM, U Chile

Title: Single-choice secretary problems with ordinal advice

When: May 17, 3:00pm.

Where: Sala de Seminario von Neuman, CMM, Beauchef 851, torre norte.

Abstract:

We examine variations of the classical secretary problem in a new setting, where the decision-maker (DM) can request one (or more) bits of ordinal information from agents before they arrive. Specifically, each agent has private information (their weight) that is publicly revealed upon arrival. As usual, the DM must irrevocably decide whether to select the agent or not after this step. Additionally, at any given time, the DM can privately ask yes-or-no questions to agents who have not yet arrived, and the agents can only answer ordinal questions based on comparing their private information with the information publicly available up to that point. We refer to this additional information as ordinal advice. For example, the DM may ask if the agent’s hidden value is higher than that of all agents who have arrived so far, but he cannot ask if that value is the largest of the entire list as the agent does not have information about the other agents that haven’t arrived.

The goal is to select the agent with the highest weight from the list. We consider different ways in which the agents can arrive, such as randomly, in an adversarial order, or with a random sample of agents that are revealed beforehand. In the latter case, the DM is the one who chooses the number of applicants included in the sample, and the rest of the input is presented in an order chosen by an adversary either before or after the realization of the sample set. We explore the impact of varying the amount of ordinal advice allowed by considering the cases where the DM can ask for zero, one, or multiple rounds of ordinal advice. We present algorithms that achieve optimal competitive ratios for almost all the settings considered. Notably, we observe that ordinal advice improves the performance in every scenario, with the exception of the adversarial-order setting.

This talk is based on joint work with José Soto.

### May 10 - 2023

Speaker: Tjark Vredeveld, Maastricht University.

Title: Learning in scheduling: simple policies for Bayesian scheduling

When: May 10, 3:00pm.

Where: Sala de Seminario von Neuman, CMM, Beauchef 851, torre norte.

Abstract:

We consider the problem of scheduling jobs on a single machine, non-preemptively. The goal is to minimize the total completion time of the jobs. It is well known that this problem is solved by scheduling the jobs in order of shortest processing times (SPT) when the jobs’ processing times are known or shortest expected processing times (SEPT), when we have full knowledge on the true expected values.

In this talk, we consider the stochastic scheduling problem in which we have additional uncertainty about the parameters of the distribution of the jobs’ processing times. We assume that jobs appear in $m$ classes and the processing times of jobs in one class are independently and identically distributed. By processing a job from one class one can learn about the true parameters of the distribution. The initial beliefs on these parameters are modelled as a prior distribution and after processing a job the posterior distribution models the updated beliefs on the parameter.

When the processing times are exponentially distributed with an unknown parameter that is gamma distributed, optimal policies based on Gittins-indices exist (see, e.g., Hamada and Glazebrook, 1993). However, computing these indices may be computationally challenging.

In this talk, we consider two simple policies, based on SEPT. The first policy processes the jobs based on the initial beliefs of the expected processing time. This implies that all jobs of one class are processed consecutively. The second policy, always processes a job from a class with shortest expected processing time according to the updated beliefs.

We can show that both policies have a (worst-case) approximation ratio of $m$, the number of classes, and that this ratio is tight.

This talk is based on (updated beliefs of) joint work with Sebastian Marban and Cyriel Rutten.

### May 3 - 2023

Speaker: Ravi Sundaram, Northeastern U.

Title: Learning to cope with adversaries (in theory) and noise (in

practice)

When: May 3, 3:00pm.

Where: Sala de Seminario von Neuman, CMM, Beauchef 851, torre norte.

Abstract:

Learning theory has burgeoned since 1971 (VC-dimension by Vapnik and Chervonenkis) when the framework was established and the fundamental theorem proved. We extend the framework to model a strategic setting that allows for adversarial behavior during the test phase. As an example consider a situation where students may manipulate their application materials knowing universities' admissions criteria. We define a new parameter, SVC (Strategic VC dimension) and use it to characterize the statistical and computational learnability of the strategic linear classification problem. The practice of learning exploded in 2012 (AlexNet by Krizhevsky, Sutskever and Hinton) leading to a profusion of deep neural network (DNN) architectures and training algorithms. We consider the problem of creating tags from a noisy scanning technology (e.g. optochemical inks, magnetic microwires etc.).

Formalizing it as a coding-theoretic problem. we develop a novel neural network architecture (DANNI) and training algorithm to solve it, with provable performance guarantees.

The theory part is joint work with Anil Vullikanti, Haifeng Xu and Fan Yao, and the practice part is joint with Akshar Varma.

### April 19 - 2023

Speaker: Evangelia Gergatsouli, University of Wisconsin - Madison

Title: Opening Pandora's Box: the Correlated Case

When: April 19, 3:00pm.

Where: Sala de Seminario von Neuman, CMM, Beauchef 851, torre norte.

Abstract:

Pandora's Box models optimization problems where the input consists of stochastic random variables, but the uncertainty can be removed (i.e. reveal the exact value of a variable) by paying an extra price. Our goal is to maximize (or minimize) the price of the variable chosen minus (resp. plus) the cost we paid to learn the exact instantiations of the variables. All previous work on this class of problems assumes that different random variables in the input are distributed independently. Until recently nothing was known for the case of correlated input.

In this talk I will introduce Pandora's Box problem and describe the first constant approximation algorithm for Pandora's Box with correlated distributions. I will also briefly mention a newer, simpler algorithm that directly generalizes the independent case algorithm while also improving on the approximation factor.

This is based on joint work with Shuchi Chawla, Yifeng Teng, Christos Tzamos and Ruimin Zhang.

### April 12 - 2023

Speaker: Ulrike Schmidt-Kraepelin, CMM.

Title: Lifting Apportionment Methods to Weighted Fair Division

When: April 12, 3:00pm.

Where: Sala de Seminario von Neuman, CMM, Beauchef 851, torre norte.

Abstract:

We study the problem of fairly allocating indivisible items to agents with different entitlements, which captures, for example, the distribution of ministries among political parties in a coalition government. This setting (known as weighted fair division) constitutes a generalization of the well-studied apportionment problem, and we present two approaches for lifting apportionment methods to weighted fair division.

In the first part of the talk, we focus on additive valuations and show that picking sequences derived from divisor methods provide natural envy-freeness, proportionality, and monotonicity properties. However, picking sequences quickly lose their fairness guarantees when moving beyond additive valuations. In the second part of the talk, we introduce welfare measures based on harmonic numbers and show that variants of maximum weighted harmonic welfare offer strong fairness guarantees under matroid-rank valuations. Surprisingly, these guarantees are even stronger than those that are satisfied by the well-known Nash welfare rule.

This talk is based on joint work with Mithun Chakraborty, Luisa Montanari, Nicholas Teh, and Warut Suksompong.

### March 22 - 2023

Speaker: Bruno Ziliotto, CNRS.

Title: Percolation games

When: March 22, 3:00pm.

Where: Sala de Seminario von Neuman, CMM, Beauchef 851, torre norte.

Abstract:

Inspired by first-passage percolation models, we consider zero-sum games on Z^d and study their limit behavior when the game duration tends to infinity. After reviewing several fundamental results in this literature, we present a generalization and discuss connections with long-term behavior of Hamilton-Jacobi equations.

### March 15 - 2023

Speaker: Jannik Matuschke, KU Leuven

Title: Decomposition of Probability Marginals for Security Games in Abstract Networks and Ideal Clutters

When: March 15, 3:00pm.

Where: Sala de Seminario von Neuman, CMM, Beauchef 851, torre norte.

Abstract: Consider a set system on a finite ground set E, where each set P in the system is equipped with a required hitting probability r(P) and each element e of E has a probability marginal p(e). We study the question whether the marginals can be decomposed into a distribution over all subsets of E such that the resulting random set intersects each set P from the system with probability at least r(P). A simple necessary condition is that for every set P in the system, the sum of the marginals of elements in P is at least r(P).

Extending a result by Dahan, Amin, and Jaillet (Mathematics of Operations Research 47:457-484, 2022) motivated by a security game in a directed acyclic graph, we show that the aforementioned necessary condition is also sufficient in the following two settings: (i) the set system fulfills a max-flow/min-cut property and the requirements are affine; (ii) the set system is an abstract network and the requirements fulfill a weak conservation law. We provide algorithms for the computation of the corresponding decompositions and, in some cases, simple explicit descriptions of these decompositions. As a subroutine, we also devise a combinatorial algorithm for computing shortest paths in abstract networks, partially answering an open question by McCormick (SODA 1996). A consequence of our results is that equilibria for the security game studied by Dahan et al. (2022) and similar games involving randomized surveillance strategies can be computed efficiently, even when the underlying digraph contains cycles.

### January 25 - 2023

Speaker: Paul Duetting, Google Research

Title: Combinatorial Contracts

When: January 25, 3:00pm hrs.

Where: Sala de Seminario von Neuman, CMM, Beauchef 851, torre norte.

Abstract: An emerging frontier in Algorithmic Game Theory is Algorithmic Contract Theory, which studies the classic hidden-action principal-agent problem of contract theory through the computational lens.

In this talk, I will present three basic ways in which the problem can be combinatorial and survey both hardness and poly-time (approximation) results.

The analysis will uncover some surprising connections (but also fundamental differences) to combinatorial auctions.

### December 15 - 2022

Speaker: Gabriel Weintraub, Stanford Graduate School of Business

Title: Experimentation in Two-Sided Marketplaces: The Impact of Interference

When: December 15, 14:30 hrs.

Where: Sala de Seminario von Neuman, CMM, Beauchef 851, torre norte.

Abstract: Marketplace platforms use experiments (also known as “A/B tests”) as a method for making data-driven decisions about which changes to make on the platform. When platforms consider introducing a new feature, they often first run an experiment to test the feature on a subset of users and then use this data to decide whether to launch the feature platform-wide. However, it is well documented that estimates of the treatment effect arising from these experiments may be biased due to the presence of interference driven by the substitution effects on the demand and supply sides of the market.

In this work, we develop an analytical framework to study experimental design in two-sided marketplaces. We develop a stochastic market model and associated mean field limit to capture dynamics in such experiments. Notably, we use our model to show how the bias of commonly used experimental designs and associated estimators depend on market balance. We also propose novel experimental designs that reduce bias for a wide range of market balance regimes. We also discuss a simpler model to study the bias-variance trade-off among different experimental choices. Finally, we present results on calibrated models and live implementations on two real-world platforms. Overall, our work shows the potential of structural modeling to yield insight on experimental design for practitioners.

Based on joint work with Ramesh Johari, Hannah Li, Inessa Liskovich, and Geng Zhao.

### December 14 - 2022

Speaker: Nick Arnosti, U Minnesota.

Title: Explainable Affirmative Action.

When: December 14, 15:00 hrs.

Where: Sala de Seminario von Neuman, CMM, Beauchef 851, torre norte.

Abstract: When organizations select from a set of applicants, they often use a priority ranking in tandem with policies designed to ensure diversity or boost the chances of applicants from certain groups. These policies add significant complexity to the selection process, and examples from around the world show that they often do not have the intended effect, or are accompanied by unintended consequences.

Motivated by a desire to make these rules more transparent, we provide three axioms intended to capture explainability: monotonicity, lower invariance, and non-bossiness. We show that these axioms characterize a family of "outcome-based" selection rules. This family of selection rules is rich enough to incorporate many (but not all) existing reserve and quota policies. We illustrate our findings using examples from the allocation of affordable housing in New York City.

### December 07 - 2022

Speaker: Dana Pizarro, UOH

Title: Competition and Recall in Selection Problems.

When: December 7, 15:00 hrs.

Where: Sala de Seminario von Neuman, CMM, Beauchef 851, torre norte.

Abstract: In this talk, I will present an extension of the prophet inequality problem to a competitive setting. At every period, a new sample from a known distribution arrives, which is publicly observed. Then, two players simultaneously decide whether to pick an available value or to pass and wait until the next period (ties are broken uniformly at random). As soon as a player gets one sample, he leaves the market, and his payoff is the value of the sample. In a first variant, namely no recall case, the agents can only bid in each period for the current value. In a second variant, the full recall case, the agents can also bid at each period for any of the previous samples that have not been already selected. For each variant, we study the two-player game induced by the optimal stopping problem, focusing on subgame-perfect Nash equilibria. In particular, I will describe the set of subgame-perfect Nash equilibria payoffs, I will compare the two model variants in terms of the payoffs of the players and I will provide tight bounds for the Price of Anarchy and Price of Stability of the former setting when the number of arrivals is two.

Joint work with Fabien Gensbittel and Jérôme Renault (TSE).

### November 30 - 2022

Speaker: Gustavo Angulo, PUC

Title: Generalized formulations for the traveling salesman problem

When: November 30, 15:00 hrs.

Where: Sala de Seminario von Neuman, CMM, Beauchef 851, torre norte.

Abstract: The traveling salesman problem is a widely studied classical combinatorial problem for which there are several integer linear formulations. In this work, we consider the Miller-Tucker-Zemlin (MTZ) formulation. First, we argue that the choice of some parameters of this formulation is arbitrary and, therefore, there is a family of formulations of which MTZ is a particular case. We analyze this family, noting that in general the formulations involved are not comparable to each other and there is no one that dominates the rest. Then, we study the intersection of this family, which we show to be equivalent to the well-known Circuit Inequalities formulation. Finally, we extend this approach to the Desrochers-Laporte and Single-Commodity Flow formulations, obtaining similar results. Based on joint work with Diego Morán (UAI).

### November 23 - 2022

Speaker: Javier Cembrano, TU Berlin

Title: Impartial Selection with Additive Guarantees via Iterated Deletion.

When: November 23, 15:00 hrs.

Where: Sala de Seminario von Neuman, CMM, Beauchef 851, torre norte.

Abstract: Impartial selection is the selection of an individual from a group based on nominations by other members of the group, in such a way that individuals cannot influence their own chance of selection. We give a deterministic mechanism with an additive performance guarantee of $O(n^{(1+\gamma)/2})$ in a setting with $n$ individuals where each individual casts $O(n^{\gamma})$ nominations, where $\gamma \in [0,1]$. For $\gamma=0$, i.e., when each individual casts at most a constant number of nominations, this bound is $O(\sqrt{n})$. This matches the best-known guarantee for randomized mechanisms and a single nomination. For $\gamma=1$ the bound is $O(n)$. This is trivial, as even a mechanism that never selects provides an additive guarantee of $n-1$. We show, however, that it is also best possible: for every deterministic impartial mechanism there exists a situation in which some individual is nominated by every other individual and the mechanism either does not select or selects an individual not nominated by anyone.

This is joint work with Felix Fischer, David Hannon, and Max Klimm.

### November 14 - 2022

Speaker: Arturo Merino, TU Berlin

Title: From Combinatorial Optimization to Combinatorial Generation.

When: November 16, 15:00 hrs.

Where: Sala de Seminario von Neuman, CMM, Beauchef 851, torre norte.

Abstract: Combinatorial generation is the task of computing all solutions to a combinatorial problem instead of only one of them. For example, we may be interested in all spanning trees of a given graph or all optimal weight perfect matchings of a given weighted graph. In recent years, there has been much interest in unifying techniques or general approaches that simultaneously apply to various combinatorial generation problems.

We propose a new simple general approach for combinatorial generation. Given some binary strings X⊆{0,1}ⁿ, our approach consists of greedily computing a Hamilton path in a polytope with X as vertices, namely conv(X). Our main result shows that this approach works for all X⊆{0,1}ⁿ and is efficient whenever optimization over X can be efficiently solved, showing an unexplored relation between combinatorial optimization and generation. More specifically, if we can solve certain linear optimization problems for X in time O(T), we can compute a Hamilton path in conv(X) in roughly O(T⋅log(n)) time per vertex.

As a consequence, we obtain new efficient algorithms for combinatorial generation problems that can be binary encoded, like spanning tree generation, 0/1 vertex enumeration, and perfect matching generation. Furthermore, consecutive objects visited by our generation algorithms differ only in a local operation, like an edge exchange in the case of spanning trees or an alternating cycle exchange in the case of perfect matchings.

This is joint work with Torsten Mütze.

### November 9 - 2022

Speaker: Alexander Kozachinskyi, IMC, UC

Title: Constant-depth sorting networks.

When: November 9, 15:00 hrs.

Where: Sala de Seminario von Neuman, CMM, Beauchef 851, torre norte.

Abstract: Assume that you want to sort n integers, and you have many copies of a device that can sort k integers. At one step, you can partition n integers into sets of size at most k by putting them into your devices. How many such steps do you need to sort your initial array?

When k = 2, this problem is just a problem of constructing a sorting network. It can be solved in O(log n) steps, though the construction is complicated and impractical. We consider a reversed setting. Namely, we fix a number of steps and seek for the minimal k such that our problem is solvable within this number of steps with this k. We determine the minimal k for 2,3, and 4 steps.

Joint work with Natalia Dobrokhotova-Maikova and Vladimir Podolski.

### October 26 - 2022

Speaker: Ana Laura Trujillo Negrete, CMM

Title: Reconstruction of token graphs

When: October 24, 15:00 hrs.

Where: Sala de Seminario von Neuman, CMM, Beauchef 851, torre norte.

Abstract: Let $G$ be a graph of order $n\ge 2$, and let $k$ be an integer with $k\in \{1,2,\dots,n-1\}$. The $k$-token graph $F_k(G)$ of $G$ is the graph whose vertices are all the $k$-subsets of vertices of $G$, and two of such $k$-subsets are adjacent whenever their symmetric difference is an edge of $G$. We denote by $C_4$ the $4$-cycle and by $D_4$ the diamond graph (a $4$-cycle with a chord). We say that $G$ is a $(C_4,D_4)$-free graph if $G$ does not contain $C_4$ nor $D_4$ as a subgraph.

In 2012 Fabila-Monroy et al. conjectured the following: If $G$ and $H$ are two graphs such that $F_k(G)$ and $F_k(H)$ are isomorphic for some $k$, then $G$ and $H$ are isomorphic. In this talk we will show this conjecture for the family of $(C_4,D_4)$-free graphs. Moreover, we will see how this reconstruction problem is related to the automorphism group of token graphs. This is a joint work with Ruy Fabila Monroy.

### October 19 - 2022

Speaker: Juan Pereyra, U. República

Title: Rawlsian Assignments

When: October 19, 15:00 hrs.

Where: Sala de Seminario von Neuman, CMM, Beauchef 851, torre norte.

Abstract: We study the assignment of indivisible objects to individuals when transfers are not allowed. Previous literature has mainly focused on efficiency (from ex-ante and ex-post perspectives), and individually fair assignments. Consequently, egalitarian concerns have been overlooked. We are inspired by the assignment of apartments in housing cooperatives where families regard the egalitarianism of the assignments as a first-order requirement. In particular, they want to avoid assignments where some families get their most preferred apartment, while others get options ranked very low in their preferences. Based on Rawls' idea of fairness, we introduce the notion of Rawlsian assignments. We prove that there always exists a unique Rawlsian assignment, which is sd-efficient, and satisfies equal treatment of equals. We illustrate our analysis with preference data from housing cooperatives. Our results show that the Rawlsian assignment substantially improves, from an egalitarian perspective, both the probabilistic serial mechanism, and the mechanism currently in use.

Joint with Tom Demeulemeester

### October 05- 2022

Speaker: Joel Joris Van de Klundert, UAI

Title: Toward Elimination of Infectious Diseases with Mobile Screening Teams: HAT in the DRC

When: October 05, 15:00 hrs.

Where: Sala de Seminario von Neuman, CMM, Beauchef 851, torre norte.

Abstract: In pursuit of Sustainable Development Goal 3 “Ensure healthy lives and promote well-being for all at all ages,” considerable global effort is directed toward elimination of infectious diseases in general and Neglected Tropical Diseases in particular. For various such diseases, the deployment of mobile screening teams forms an important instrument to reduce prevalence toward elimination targets. There is considerable variety in planning methods for the deployment of these mobile teams in practice, but little understanding of their effectiveness. Moreover, there appears to be little understanding of the relationship between the number of mobile teams and progress toward the goals. This research considers capacity planning and deployment of mobile screening teams for one such neglected tropical disease: Human African trypanosomiasis (HAT, or sleeping sickness). We prove that the deployment problem is strongly NP-Hard and propose three approaches to find (near) optimal screening plans. For the purpose of practical implementation in remote rural areas, we also develop four simple policies. The performance of these methods and their robustness is benchmarked for a HAT region in the Democratic Republic of Congo (DRC). Two of the four simple practical policies yield near optimal solutions, one of which also appears robust against parameter impreciseness. We also present a simple approximation of prevalence as a function of screening capacity, which appears rather accurate for the case study. While the results may serve to more effectively allocate funding and deploy mobile screening capacity, they also indicate that mobile screening may not suffice to achieve HAT elimination.

### September 28- 2022

Speaker: Denae Ventura, UNAM

Title: Recursive local amoeba construction.

When: September 28, 15:00 hrs.

Where: Sala de Seminario von Neuman, CMM, Beauchef 851, torre norte.

Abstract: Amoeba graphs were born as examples of balanceable graphs, which are graphs that appear in any 2-edge coloring of the edges of a large enough $K_n$ with a sufficient amount of red and blue edges. As they were studied further, interesting aspects were found.

An edge replacement $e\to e$ in a labeled graph G means to take an edge e in E(G) and replace it with e' \in E(\overline{G})\cup \{e\}$. If $G-e+e'$ is isomorphic to $G$ then we say $e\to e'$ is a \emph{feasible edge replacement}. Every edge replacement yields a set of permutations of the labels in $G$. The set of all permutations associated with all feasible edge replacements in $G$ generates the group $\Gamma_G$. A labeled graph $G$ of order $n$ is a \emph{local amoeba} if $\Gamma_G \cong S_n$. One might think local amoebas are hard to find. However, in this talk we will go over a recursive construction of infinite families of local amoebas.

Es trabajo conjunto con Ludmila Matyskova

### September 21- 2022

Speaker: Alfonso Montes

Title: Bayesian Persuasion With Costly Information Acquisition.

When: September 21, 15:00 hrs.

Where: Sala de Seminario von Neuman, CMM, Beauchef 851, torre norte.

Abstract: We consider a Bayesian persuasion model in which the receiver can gather independent information about the state at a uniformly posterior-separable cost. We show that the sender provides information that prevents the receiver from gathering independent information in equilibrium. When the receiver faces a lower cost of information, her `threat' of gathering independent information increases, thus decreasing the sender's power to persuade. A lower cost of information can also hurt the receiver because the sender may provide strictly less information in equilibrium. Finally, we propose a solution method that can be used to solve our model in specific applications.

Es trabajo conjunto con Ludmila Matyskova

### September 07- 2022

Speaker: Felipe Subiabre, U Chile

Title: The kidney exchange problem: length-constrained cycles and chains optimization on compatibility graphs

When: September 7, 15:00 hrs.

Where: Sala de Seminario von Neuman, CMM, Beauchef 851, torre norte.

Abstract: The kidney exchange problem is a combinatorial optimization problem that arises naturally when implementing centralized kidney exchange programs. Given a directed weighted graph (called the compatibility graph), we aim to find a collection of simple and vertex-disjoint cycles maximizing the total weight of their participating arcs.

Because of logistical considerations, a bound k is placed on the length of each possible cycle. We will briefly explain how the problem is polynomially solvable in the cases k = 2 and unbounded k, and why it turns NP-complete for k >= 3.

MIP formulations are used in practice because of their efficiency and flexibility to accommodate extra constraints of the exchange programs. We will introduce the cycles MIP formulation of Roth et al. and explain why its linear relaxation is polynomially solvable. Inspired by this result, we present a conjecture on the integrality gap of this formulation, which is part of our ongoing work.

Time permitting, we will also discuss the addition of exchange chains starting from a distinguished subset of vertices (representing deceased or altruistic donors) and explain how their introduction makes even the associated linear relaxation problem NP-hard.

### August 24- 2022

Speaker: Laura Vargas Koch, U Chile

Title: Solidarity Cover Problem

When: August 24, 14:30 hrs.

Where: Sala de Seminario von Neuman, CMM, Beauchef 851, torre norte.

Abstract: This work started with a real-world problem where the task was to partition a set of locations into disjoint subsets such that each subset is spread in a way that it covers the whole set with a certain radius.

This made us formalizing the following problem which we call Solidarty Cover Problem. Given a finite set S, a metric d, and a radius r, and a number of partitions m. We define a subset C of S to be an r-cover if B(C,r)=S. The Solidarity Cover Problem is the problem of determining whether there exist m disjoint r-covers. We consider the optimization problems of maximizing the number of r-covers which is essentially the domatic number problem, and the optimization problem of minimizing the radius.

This is joint work with Britta Peis and Eran Rosenbluth.

### August 17 - 2022

Speaker: Alexandros Tsigonias-Dimitriadis, TUM

Title: Prophet Inequalities via the Expected Competitive Ratio

When: August 17, 15:00 hrs.

Where: Sala de Seminario von Neuman, CMM, Beauchef 851, torre norte.

Abstract: We consider prophet inequalities under general downward-closed constraints. In a prophet inequality problem, a decision-maker sees a series of online elements and needs to decide immediately and irrevocably whether or not to select each element upon its arrival, subject to an underlying feasibility constraint. Traditionally, the decision-maker’s expected performance has been compared to the expected performance of the prophet, i.e., the expected offline optimum. We refer to this measure as the Ratio of Expectations (or, in short, RoE). However, a major limitation of the RoE measure is that it only gives a guarantee against what the optimum would be on average, while, in theory, algorithms still might perform poorly compared to the realized ex-post optimal value.

Hence, we study alternative performance measures. In particular, we suggest the Expected Ratio (or, in short, EoR), which is the expectation of the ratio between the value of the algorithm and the value of the prophet. This measure yields desirable guarantees, e.g., a constant EoR implies achieving a constant fraction of the ex-post offline optimum with constant probability. Moreover, in the single-choice setting, we show that the EoR is equivalent (in the worst case) to the probability of selecting the maximum, a well-studied measure in the literature. This is no longer the case for combinatorial constraints (beyond single-choice), which is the main focus of this paper.

Our main goal is to understand the relation between RoE and EoR in combinatorial settings. Specifically, we establish a two-way black-box reduction: for every feasibility constraint, the RoE and the EoR are at most a constant factor apart. This implies a wealth of EoR results in multiple settings where RoE results are known.

This is joint work with Tomer Ezra, Stefano Leonardi, Rebecca Reiffenhäuser, and Matteo Russo.

### July 27- 2022

Speaker: Waldo Gálvez, UOH

Title: Machine Covering in the Random-Order Model

When: July 27, 15:00 hrs.

Where: Sala de Seminario von Neuman, CMM, Beauchef 851, torre norte.

Abstract: In the Online Machine Covering problem, jobs, defined by their sizes, arrive one by one and have to be assigned to m parallel and identical machines, with the goal of maximizing the load of the least-loaded machine. Unfortunately, the classical model allows only fairly pessimistic performance guarantees: The best possible deterministic ratio of m is achieved by the Greedy-strategy, and the best known randomized algorithm has competitive ratio Õ(m^(1/2)), which cannot be improved by more than a logarithmic factor.

In this talk, we will discuss results for the Machine Covering problem in the random-order model. Here, no extra resources are present but, instead, the adversary is weakened in that it can only decide upon the input set while jobs are revealed uniformly at random. It is particularly relevant to Machine Covering where lower bounds usually come from highly structured input sequences.

We first analyze Graham's Greedy-strategy in this context and show that its competitive ratio decreases slightly to O(m/log(m)), which is asymptotically tight. Then, we will present an improved Õ(m^(1/4))-competitive algorithm for the problem. This result is achieved by exploiting the extra information coming from the random order of the jobs, using sampling techniques to devise an improved mechanism to distinguish jobs that are relatively large from small ones. Time permitting, we will also present a lower bound, showing that no algorithm can have a competitive ratio of O(log(m)/loglog(m)) in the random-order model. This lower bound is achieved by studying a variant of the Secretary problem.

Joint work with Susanne Albers and Maximilian Janke.

### June 1 - 2022

Speaker: Benjamín Rubio, UC

Title: Searching infected nodes in uncertain graphs

When: June 1, 15:00 hrs.

Where: Sala de Seminario von Neuman, CMM, Beauchef 851, torre norte.

Abstract: In the context of the COVID-19, the development of methods to trace the spread of the virus is of vital importance. One of such methods relies on PCR testing of wastewater samples to locate sudden the appearance of infection. Given a representation of the wastewater network as a directed graph, we aim for a strategy that finds a new infected node using the worst-case minimum number of tests. This problem proves to be challenging on networks with uncertainty, as is the case of real-world data. We will explore the connection with other known graph problems and show upper bounds for the number of tests in an optimal strategy on graphs of bounded treewidth and planar graphs. Then we analyze experimental results obtained using a greedy algorithm to select nodes to sample, and finally conclude by stating several relevant open questions.

Joint work with I. Beaudry, J. Baboun, M. Castro, A. Jara, B. Rubio, J. Verschae.

### July 20 - 2022

Speaker: Bernardo Subercaseaux, Carnegie Mellon U.

Title: Augmenting Online Algorithms with ε-Accurate Predictions.

When: July 20, 15:00 hrs.

Where: Sala de Seminario von Neuman, CMM, Beauchef 851, torre norte.

Abstract: The growing body of work in learning-augmented online algorithms studies how online algorithms can be improved when given access to ML predictions about the future. Motivated by ML models that give a confidence parameter for their predictions, we study online algorithms with predictions that are $\epsilon$-accurate: namely, each prediction is correct with probability (at least) $\epsilon$, but can be arbitrarily inaccurate with the remaining probability. We show that even with predictions that are accurate with a small probability and arbitrarily inaccurate otherwise, we can dramatically outperform worst-case bounds for a range of classical online problems including caching, online set cover, and online facility location. Our main results are an $O(\log(1/\varepsilon))$-competitive algorithm for caching, and a simple $O(1/\varepsilon)$-competitive algorithm for a large family of covering problems, including set cover and facility location, with $\epsilon$-accurate predictions.

### June 1 - 2022

Speaker: Benjamín Rubio, UC

Title: Searching infected nodes in uncertain graphs

When: June 1, 15:00 hrs.

Where: Sala de Seminario von Neuman, CMM, Beauchef 851, torre norte.

Abstract: In the context of the COVID-19, the development of methods to trace the spread of the virus is of vital importance. One of such methods relies on PCR testing of wastewater samples to locate sudden the appearance of infection. Given a representation of the wastewater network as a directed graph, we aim for a strategy that finds a new infected node using the worst-case minimum number of tests. This problem proves to be challenging on networks with uncertainty, as is the case of real-world data. We will explore the connection with other known graph problems and show upper bounds for the number of tests in an optimal strategy on graphs of bounded treewidth and planar graphs. Then we analyze experimental results obtained using a greedy algorithm to select nodes to sample, and finally conclude by stating several relevant open questions.

Joint work with I. Beaudry, J. Baboun, M. Castro, A. Jara, B. Rubio, J. Verschae.

### July 13 - 2022

Speaker: Tomás González, IMC, UC.

Title: Differentially Private Stationary Points in Stochastic Nonconvex Optimization

When: July 13, 15:00 hrs.

Where: Sala de Seminario von Neuman, CMM, Beauchef 851, torre norte.

Abstract: Differentially private (DP) stochastic nonconvex optimization (SNCO) is a fundamental problem, where the goal is to approximate stationary points (i.e points with small norm of the gradient) of the population loss, given a dataset of i.i.d. samples from a distribution, while satisfying differential privacy with respect to the dataset. Most of the existing works in the literature have addressed either the convex version of this problem (DP-SCO) or the closely related problem of Private Non-Convex Empirical Risk Minimization, where one seeks to approximate stationary points of the empirical loss.

In the first part of this talk I will provide an overview of differential privacy and of (non-private) stochastic nonconvex optimization. Then, I will show how to privatize the well known SPIDER algorithm for SNCO that relies on variance reduction techniques, and how to prove privacy and accuracy guarantees for its private version. The private version of SPIDER leads to the rate of convergence to stationary points of the population loss of O(d^{1/4} / (n\epsilon)^{1/2}), which was the best previously known rate for the empirical case.

The private version of SPIDER appeared in section 4 of arXiv:2206.00846.

### July 06 - 2022

Speaker: Niklas Rieken, RWTH Aachen.

Title: Computing buyer-optimal Walrasian prices in multi-unit matching markets via a sequence of max flow computations

When: July 06, 15:00 hrs.

Where: Sala de Seminario von Neuman, CMM, Beauchef 851, torre norte.

Abstract: Given a market where discrete indivisible items of different types are sold to a set of buyers. There is a given supply of each type and each buyer has a given (maximum) demand. Each buyer valuates the items linearly in our setting. We aim for competitive prices, i.e. prices such that an allocation exists where every buyer gets one of his preferred bundles. The prices should be as small as possible and as much as possible should be sold.

We show how to compute these buyer-optimal Walrasian prices. We present an ascending auction which iteratively raises the prices on the goods in the left-most min cut in some associated auxiliary flow network. Given this prices, we can compute an allocation where as much as possible is sold. The structural insights obtained from our flow-based approach furthermore lead to several interesting insights regarding the sensitivity analysis of our ascending auction.

Joint work with Katharina Eickhoff, Tom McCormick, Britta Peis, and Laura Vargas Koch.

### June 29 - 2022

Speaker: Pablo Barcelo, Instituto de Ingeniería Matemática y Computacional (IMC), UC

Title: The AGM Bound

When: June 29, 15:00 hrs.

Where: Sala de Seminario von Neuman, CMM, Beauchef 851, torre norte.

Abstract: In several computer science applications one encounters the following problem: Given two edge-labeled graphs G and H, how many homomorphic images of H can be found in G? Atserias, Grohe, and Marx developed a tight bound for this number, denoted #Hom(H,G), which is now known as the AGM bound. The bound relates #Hom(H,G) with the fractional edge covers of H in a very elegant and direct way. We will present a self-contained and simple proof of this result using Shearer's inequality.

### May 25- 2022 (POSTPONED)

Speaker: Waldo Gálvez, UOH

Title: Machine Covering in the Random-Order Model

When: May 25, 15:00 hrs.

Where: Sala de Seminario von Neuman, CMM, Beauchef 851, torre norte.

Abstract: In the Online Machine Covering problem, jobs, defined by their sizes, arrive one by one and have to be assigned to m parallel and identical machines, with the goal of maximizing the load of the least-loaded machine. Unfortunately, the classical model allows only fairly pessimistic performance guarantees: The best possible deterministic ratio of m is achieved by the Greedy-strategy, and the best known randomized algorithm has competitive ratio Õ(m^(1/2)), which cannot be improved by more than a logarithmic factor.

In this talk, we will discuss results for the Machine Covering problem in the random-order model. Here, no extra resources are present but, instead, the adversary is weakened in that it can only decide upon the input set while jobs are revealed uniformly at random. It is particularly relevant to Machine Covering where lower bounds usually come from highly structured input sequences.

We first analyze Graham's Greedy-strategy in this context and show that its competitive ratio decreases slightly to O(m/log(m)), which is asymptotically tight. Then, we will present an improved Õ(m^(1/4))-competitive algorithm for the problem. This result is achieved by exploiting the extra information coming from the random order of the jobs, using sampling techniques to devise an improved mechanism to distinguish jobs that are relatively large from small ones. Time permitting, we will also present a lower bound, showing that no algorithm can have a competitive ratio of O(log(m)/loglog(m)) in the random-order model. This lower bound is achieved by studying a variant of the Secretary problem.

Joint work with Susanne Albers and Maximilian Janke.

### June 1 - 2022

Speaker: Benjamín Rubio, UC

Title: Searching infected nodes in uncertain graphs

When: June 1, 15:00 hrs.

Where: Sala de Seminario von Neuman, CMM, Beauchef 851, torre norte.

Abstract: In the context of the COVID-19, the development of methods to trace the spread of the virus is of vital importance. One of such methods relies on PCR testing of wastewater samples to locate sudden the appearance of infection. Given a representation of the wastewater network as a directed graph, we aim for a strategy that finds a new infected node using the worst-case minimum number of tests. This problem proves to be challenging on networks with uncertainty, as is the case of real-world data. We will explore the connection with other known graph problems and show upper bounds for the number of tests in an optimal strategy on graphs of bounded treewidth and planar graphs. Then we analyze experimental results obtained using a greedy algorithm to select nodes to sample, and finally conclude by stating several relevant open questions.

Joint work with I. Beaudry, J. Baboun, M. Castro, A. Jara, B. Rubio, J. Verschae.

### May 18 - 2022

Speaker: Pawel Pralat, Ryerson University.

Title: Semi-random process

When: May 18, 15:00 hrs.

Where: https://zoom.us/j/98780407155?pwd=MnR3dGlab2dkcU0xVFprTFRKcnptZz09

Abstract: The semi-random graph process is a single-player game that begins with an empty graph on n vertices. In each round, a vertex u is presented to the player independently and uniformly at random. The player then adaptively selects a vertex v and adds the edge uv to the graph. For a fixed monotone graph property, the objective of the player is to force the graph to satisfy this property with high probability in as few rounds as possible.

During the talk, we will focus on the following problems: a) perfect matchings, b) Hamilton cycles, c) constructing a subgraph isomorphic to an arbitrary fixed graph G. We will also consider a natural generalization of the process to s-uniform hypergraphs.

### May 11 - 2022

Speaker: Federico Echeñique, Caltech.

Title: Efficiency and fairness in random resource allocation and social choice

When: May 11, 15:00 hrs.

Where: Sala de Seminario von Neuman, CMM, Beauchef 851, torre norte.

Abstract: We study efficiency in general collective choice problems when agents have ordinal preferences, and randomization is allowed. We establish the equivalence between welfare maximization and ex-ante efficiency for general domains, and relate ex-ante efficiency with ex-post efficiency, characterizing when the two notions coincide. We also propose a new general notion of fairness that is applicable in any social choice environment, not only in resource allocation. Our results have implications for well-studied mechanisms including random serial dictatorship and a number of specific environments, including the dichotomous, single-peaked, and social choice domains.

Joint work with Joe Root and Fedor Sandomirskiy.

### April 20 - 2022

Speaker: Tobias Mömke, U. Ausburg

Title: A PTAS for Unsplittable Flow on a Path

When: April 20, 14:00 hrs.

Where: Sala de Seminario von Neuman, CMM, Beauchef 851, torre norte.

Abstract: In the Unsplittable Flow on a Path problem (UFP) we are given a path with edge capacities, and a set of tasks where each task is characterized by a subpath, a demand, and a weight. The goal is to select a subset of tasks of maximum total weight such that the total demand of the selected tasks using each edge e is at most the capacity of e. The problem admits a QPTAS [Bansal, Chakrabarti, Epstein, Schieber, STOC'06; Batra, Garg, Kumar, Mömke, Wiese, SODA'15]. After a long sequence of improvements [Bansal, Friggstad, Khandekar, Salavatipour, SODA'09; Bonsma, Schulz, Wiese, FOCS'11; Anagnostopoulos, Grandoni, Leonardi, Wiese, SODA'14; Grandoni, Mömke, Wiese, Zhou, STOC'18], the best known polynomial time approximation algorithm for UFP has an approximation ratio of 1+1/(e+1) + epsilon < 1.269 [Grandoni, Mömke, Wiese, SODA'22]. It has been an open question whether this problem admits a PTAS. In this paper, we solve this open question and present a polynomial time (1 + epsilon)-approximation algorithm for UFP.

### April 20 - 2022

Speaker: Dieter Mitsche, PUC

Title: Percolation on dense random graphs with given degrees.

When: April 20, 15:00 hrs.

Where: Sala de Seminario von Neuman, CMM, Beauchef 851, torre norte.

Abstract: We study the order of the largest connected component of a random graph having two sources of randomness: first, the graph is chosen randomly from all graphs with a given degree sequence, and then bond percolation is applied. Far from being able to classify all such degree sequences, we exhibit several new threshold phenomena for the order of the largest component in terms of both sources of randomness. We also provide an example of a degree sequence, for which the order of the largest component undergoes an unbounded number of jumps in terms of the percolation parameter, giving rise to a behavior that cannot be observed without percolation.

Joint work with Lyuben Lichev and Guillem Perarnau.

### April 13 - 2022

Speaker: Andrés Fielbaum, TU Delft

Title: How to split the costs and charge the travellers sharing a ride? aligning system’s optimum with users’ equilibrium

When: April 13, 15:00 hrs.

Where: Sala de Seminario von Neuman, CMM, Beauchef 851, torre norte.

Abstract: Emerging on-demand sharing alternatives, in which one resource is utilised simultaneously by a circumstantial group of users, entail several challenges regarding how to coordinate such users. A very relevant case refers to how to form groups in a mobility system that offers shared rides, and how to split the costs within the travellers of a group. These are non-trivial tasks, as two objectives conflict: 1) minimising the total costs of the system, and 2) finding an equilibrium where each user is content with her assignment. Aligning both objectives is challenging, as users are not aware of the externalities induced to the rest.

In this paper, we propose protocols to share the costs within a ride so that optimal solutions can also constitute equilibria. To do this, we model the situation as a non-cooperative game, which can be seen as a game-version of the well-known set cover problem. We show that the traditional notions of equilibrium in game theory (Nash and Strong) are not useful here, and prove that determining whether a Strong Equilibrium exists is an NP-Complete problem, by reducing it to the k-Exact-Cover problem. Hence, we propose three alternative equilibrium notions (stronger than Nash and weaker than Strong), depending on how users can coordinate. For each of these equilibrium notions, we propose a (possibly overcharging) cost-sharing protocol that yields the optimal solutions equilibria.

Simulations for Amsterdam reveal that our protocols can achieve stable solutions that are close to the optimum, and that having a central coordinator can have a large impact.

### April 6 - 2022

Speaker: Frederik Mallmann-Trenn, King's College

Title: Finding the best papers with noisy reviews

When: April 6, 15:00 hrs.

Where: Sala de Seminario von Neuman, CMM, Beauchef 851, torre norte.

Abstract: Say you are tasked to find the best 150 papers among more than 250 for conference proceedings or as part of a national exercise to maximise workload.

You can ask people to review a given paper by either asking

1) Is paper A better than paper B

or

2) What’s the score of paper A?

The problem is that each review returns an incorrect response with a small probability, say 1/3.

How can you assign reviews so that you will likely find the best 150 papers while the total of queries and rounds is small?

The talk is based on the paper

Instance-Optimality in the Noisy Value-and Comparison-Model---Accept, Accept, Strong Accept: Which Papers get in? [SODA 2020]

https://epubs.siam.org/doi/10.1137/1.9781611975994.131

https://arxiv.org/pdf/1806.08182.pdf

### March 30 - 2022

Speaker: Laura Vargas Koch, CMM

Title: Nash Flows over Time: Uniqueness, Continuity and Long-term behavior

When: March 30, 15:00 hrs (Chilean time).

Where: Sala de Seminario von Neuman, CMM, Beauchef 851, torre norte.

Abstract: In the talk, we consider a dynamic model of traffic that has received a lot of attention in the past few years, Nash Flows over time.

Users control infinitesimal flow particles aiming to travel from a source to destination as quickly as possible.

Flow patterns vary over time, and congestion effects are modeled via queues, which form whenever the inflow into a link exceeds its capacity.

We will see that assuming constant inflow into the network at the source, equilibria always settle down into a "steady state'' in which the behavior extends forever in a linear fashion. This extends a result of Cominetti, Correa and Olver, who show a steady-state result in the regime where the input flow rate is smaller than the network capacity.

Surprisingly, the steady state result turns out to be helpful to prove two nice properties:

- Uniqueness of journey times in equilibria

- Continuity of equilibria: small perturbations to the instance or to the traffic situation at some moment cannot lead to wildly different equilibrium evolutions.

This is joint work with Neil Olver and Leon Sering

### March 23 - 2022

Speaker: Victor Verdugo, Universidad de O'Higgins

Title: A 2-Approximation for the Bounded Treewidth Sparsest Cut Problem in FPT Time

When: March 23, 15:00 hrs (Chilean time).

Abstract: In the non-uniform sparsest cut problem, we are given a supply graph G and a demand graph D, both with the same set of nodes V. The goal is to find a cut of V that minimizes the ratio of the total capacity on the edges of G crossing the cut over the total demand of the crossing edges of D. In this work, we study the non-uniform sparsest cut problem for supply graphs with bounded treewidth k. For this case, Gupta, Talwar and Witmer [STOC 2013] obtained a 2-approximation with polynomial running time for fixed k, and the question of whether there exists a c-approximation algorithm for a constant c independent of k, which runs in FPT time, remained open. We answer this question in the affirmative. We design a 2-approximation algorithm for the non-uniform sparsest cut with bounded treewidth supply graphs that runs in FPT time when parameterized by the treewidth. Our algorithm is based on rounding the optimal solution of a linear programming relaxation inspired by the Sherali-Adams hierarchy. In contrast to the classic Sherali-Adams approach, we construct a relaxation driven by a tree decomposition of the supply graph by including a carefully chosen set of lifting variables and constraints to encode information of subsets of nodes with super-constant size, and at the same time we have a sufficiently small linear program that can be solved in FPT time.

This is joint work with Vincent Cohen-Addad (Google Research Zurich) and Tobias Mömke (University of Augsburg). This work has been accepted at IPCO 2022.

### July 09 - 2021

Speaker: Christoph Dürr, Sorbonne Université

Title: Orienting (hyper)graphs under explorable stochastic uncertainty

When: August 11, 14:30 hrs (Chilean time).

Link: https://zoom.us/j/99541270241?pwd=Tm51dVdlRWFNNmVQRHdQdWh6dEJmQT09

Abstract: Given a hypergraph with uncertain node weights following known probability distributions, we study the problem of querying as few nodes as possible until the identity of a node with minimum weight can be determined for each hyperedge. Querying a node has a cost and reveals the precise weight of the node, drawn from the given probability distribution. Using competitive analysis, we compare the expected query cost of an algorithm with the expected cost of an optimal query set for the given instance. For the general case, we give a polynomial-time f(α)-competitive algorithm, where f(α)∈[1.618+ϵ,2] depends on the approximation ratio α for an underlying vertex cover problem. We also show that no algorithm using a similar approach can be better than 1.5-competitive. Furthermore, we give polynomial-time 4/3-competitive algorithms for bipartite graphs with arbitrary query costs and for hypergraphs with a single hyperedge and uniform query costs, with matching lower bounds.

Joint work with Evripidis Bampis, Thomas Erlebach, Murilo S. de Lima, Nicole Megow, Jens Schlöter.

### July 07 - 2021

Speaker: Jannik Matuschke, KU Leuven.

Title: Generalized Malleable Scheduling via Discrete Concavity

When: June 30, 14:30 hrs (Chilean time).

Link: https://zoom.us/j/93921286620?pwd=MTRCdzJuY3ZRUVhRVnlkNEtuc2k2UT09

Abstract: In malleable scheduling, jobs can be executed simultaneously on multiple machines with the processing time depending on the number of allocated machines. Each job is required to be executed non-preemptively and in unison, i.e., it has to occupy the same time interval on all its allocated machines.

In this talk, we discuss a generalization of malleable scheduling, in which a function f(S, j) determines the processing time of job j on machine subset S. Under different discrete concavity assumptions on 1/f(S,j), we show that the scheduling problem can be approximated by a considerably simpler assignment problem and derive LP-based approximation algorithms.

We also highlight a connection to the problem of fairly allocating resources (the Santa Claus problem and its generalizations) and show how our results imply resource-augmented approximation algorithms for this setting.

This is joint work with Dimitris Fotakis and Orestis Papadigenopoulos.

### June 30 - 2021

Speaker: Stijn Cambie, Raboud University Nijmegen.

Title: On the general problem of Erdos and Nesetril and its offsprings

When: June 30, 14:30 hrs (Chilean time).

Link: https://zoom.us/j/96139597495?pwd=YzFtak9oRElYN3Mra2NCUmRMMlkyUT09

Abstract: In 1988, Erdos wrote about a problem he proposed with Nesetril:

"One could perhaps try to determine the smallest integer h_t(D) for which every graph, with size h_t(D) edges and maximum degree at most D, contains two edges so that the shortest path joining these edges has length at least t. This problem seems to be interesting only if there is a nice expression for h_t(D)."

This problem can be considered as the edge version of the famous (and hard) degree-diameter problem.

It was the inspiration for a series of research papers on variants of this problem, where one is mainly dealing with the case t=2. We will discuss part of the history that resulted in the strong edge colouring conjecture, which is still widely open.

In the second part of the talk, we will look again to the initial inspirational question of all of this and say more about the cases where t is at least 3.

### June 23 - 2021

Speaker: Andrés Perlroth, Google Research.

Title: Auctions with Intermediaries

When: June 23, 14:30 hrs (Chilean time).

Link: https://zoom.us/j/98113903152?pwd=NGdlUVo4TUx0bVVSYzVUUUFjR1RFUT09

Abstract: In many markets, buyers do not bid directly in the auction, but instead, they are represented by intermediaries. This includes ad auctions, where some of the buyers might be represented by intermediaries like Ad agencies, Aggregators (e.g. Home Advisor), or Ad networks participating in an Ad Exchange. The presence of intermediaries creates the potential for collusion across buyers. Also, intermediaries have their own goals that depend on the contract between buyers and the intermediary, and will behave according to the incentives induced by their goals. We will talk about the problem of designing mechanisms for such settings. In particular, we consider the problem of selling k items to unit-demand buyers with private valuations for the items. A buyer either participates directly in the auction or is represented by an intermediary, who can represent a subset of buyers. Our goal is to design robust mechanisms that are independent of the demand structure (i.e. how the buyers are partitioned across intermediaries), and perform well under a wide variety of possible contracts between intermediaries and buyers. We first consider the case of k identical items where each buyer draws its private valuation for an item i.i.d. from a known distribution that is lambda-regular (a weaker condition than monotone hazard rate). Next, we generalize this to the setting of related items.

### June 16 - 2021

Speaker: Yuri Faenza, Columbia U.

Title: Some discrete optimization problems in matching markets

When: June 16, 14:30 hrs (Chilean time).

Link: https://zoom.us/j/93599820111?pwd=djhyZGRGTzhiY3ZVdDNSN05PekdQQT09

Abstract: In the classical stable marriage problem, we are given two sets of agents - students and schools - with each student and school having a total order of agents from the opposite set. The goal is to form disjoint pairs of students and schools so that the resulting matching satisfies a fairness property known as stability. In their fundamental work, Gale and Shapley showed that a stable matching always exists, and gave a fast algorithm to find one. These strong structural and algorithmic results propelled the application of the stable marriage model in several contexts, most notably for assigning students to public high schools in many cities in the United States. Although very successful, the marriage model however fails to capture features that have become of crucial importance both inside and outside academia, such as diversity in school cohorts, complex preference patterns, and the need to obtain larger, possibly mildly unstable, matchings. In this talk, I will first present some extensions of the concept of stability and of the marriage model, and investigate them from an optimizer's viewpoint. I will then focus in detail on recent work with Xuan Zhang (Columbia) on algorithms for stable matching models when the preference patterns of agents are described by choice functions. Our approach will allow us to deduce general sufficient conditions for efficiently optimizing linear functions over the elements of a distributive lattice.

### June 09 - 2021

Speaker: Raimundo Saona, IST Austria.

Title: Stability in Matrix Games

When: June 09, 14:30 hrs (Chilean time).

Link: https://zoom.us/j/95009019759?pwd=K1VQSUhjSGhMOFpPQWJNY0NxcnFIZz09

Abstract: We consider the simplest game, Matrix Games, and basic stability questions on the value and strategies upon perturbations on the payoff matrix. Considering polynomial perturbations, we design polynomial-time algorithms for the following tasks: (a) ensuring that, for every sufficiently small error, there is a strategy to guarantee that the value is at least the value of the error-free case; (b) ensuring that there is a fixed strategy to guarantee that, for every sufficiently small error, the value is at least the value of the error-free case; and (c) computing the analytical form of the value of the game upon perturbations. We also make the connection with Linear Programming, just as Mills did in 1956 for a related problem.

### June 09 - 2021

Speaker: David Conlon, Caltech.

Title: Random multilinear maps and the Erdős box problem

When: June 08, 16:30 hrs (Chilean time).

Link: https://us02web.zoom.us/j/87593953555?pwd=UWl4eTVsanpEUHJDWFo3SWpNNWtxdz09

Abstract: By using random multilinear maps, we provide new lower bounds for the Erdős box problem, the problem of estimating the extremal number of the complete d-partite d-uniform hypergraph with two vertices in each part, thereby improving on work of Gunderson, Rödl and Sidorenko. Joint work with Cosmin Pohoata and Dmitriy Zakharov.

### June 02 - 2021

Speaker: Ulrike Schmidt-Kraepelin, TU Berlin

Title: Popular Branchings and Their Dual Certificates

When: June 02, 14:30 hrs (Chilean time).

Link: https://zoom.us/j/93628970125?pwd=L1l6cTVXOVY4Rmh6MllnR2FHanRWUT09

Abstract: Let G be a digraph where every node has preferences over its incoming edges. The preferences of a node extend naturally to preferences over branchings, i.e., directed forests; a branching B is popular if B does not lose a head-to-head election (where nodes cast votes) against any branching. Such popular branchings have a natural application in liquid democracy. The popular branching problem is to decide if G admits a popular branching or not. We give a characterization of popular branchings in terms of dual certificates and use this characterization to design an efficient combinatorial algorithm for the popular branching problem. When preferences are weak rankings, we use our characterization to formulate the popular branching polytope in the original space and also show that our algorithm can be modified to compute a branching with least unpopularity margin. When preferences are strict rankings, we show that “approximately popular” branchings always exist.

This is joint work with Telikepalli Kavitha, Tamás Király, Jannik Matuschke, and Ildikó Schlotter.

### May 12 - 2021

Speaker: Waldo Galvez, TU Munich

Title: Improved Approximation Algorithms for 2-Dimensional Knapsack: Packing into Multiple L-Shapes, Spirals, and More

When: May 12, 14:30 hrs (Chilean time).

Link: https://zoom.us/j/95062692613?pwd=YWF2QSsvNVZ5WERYeG1GOXNvMmtMQT09

Abstract: In the 2-Dimensional Knapsack problem (2DK) we are given a square knapsack and a collection of n rectangular items with integer sizes and profits. Our goal is to find the most profitable subset of items that can be packed non-overlappingly into the knapsack. The currently best known polynomial-time approximation factor for 2DK is 17/9+eps<1.89 and there is a (3/2+eps)-approximation algorithm if we are allowed to rotate items by 90 degrees. In this talk, I will present a (4/3+eps)-approximation algorithms in polynomial time for both cases, assuming that all input data are integers polynomially bounded in n.

The previous best algorithm for 2DK partitions the knapsack into a constant number of rectangular regions plus one L-shaped region and packs items into those in a structured way. We generalize this approach by allowing up to a constant number of more general regions that can have the shape of an L, a U, a Z, a spiral, and more, and therefore obtain an improved approximation ratio. In particular, our results are achieved via an algorithm that computes the essentially optimal structured packing into these regions.

Joint work with Fabrizio Grandoni, Arindam Khan, Diego Ramírez-Romero and Andreas Wiese.

### May 5 - 2021

Speaker: Cristóbal Guzmán, U Twente

Title: Non-Euclidean Differentially Private Stochastic Convex Optimization

When: May 5, 14:30 hrs (Chilean time).

Link: https://zoom.us/j/98855281600?pwd=Z3A4bGMvSGFwQnl5OXhOWE41UVNIQT09

Abstract: Differentially private (DP) stochastic convex optimization (SCO) is a fundamental problem, where the goal is to approximately minimize the population risk with respect to a convex loss function, given a dataset of i.i.d. samples from a distribution, while satisfying differential privacy with respect to the dataset. Most of the existing works in the literature of private convex optimization focus on the Euclidean (i.e., $\ell_2$) setting, where the loss is assumed to be Lipschitz (and possibly smooth) w.r.t.~the $\ell_2$ norm over a constraint set with bounded $\ell_2$ diameter. Algorithms based on noisy stochastic gradient descent (SGD) are known to attain the optimal excess risk in this setting.

In this talk I will provide a brief overview of differential privacy and its applications in stochastic convex optimization, together with new upper and lower bounds on the population risk for DP-SCO in non-Euclidean setups, in particular where the reference norm is the $\ell_p$-norm, $1\leq p\leq \infty$. Our algorithms include DP versions of variance-reduced stochastic Frank-Wolfe and mirror-descent methods, together with a novel privacy mechanism, which generalizes the Gaussian mechanism. Our work draws upon concepts from the geometry of normed spaces, such as the notions of regularity, uniform convexity, and uniform smoothness.

Based on joint work with Raef Bassily and Anupama Nandi, and available at arXiv:2103.01278

### April 28 - 2021

Speaker: Nicolas Rivera, Universidad de Valparaiso

Title: The Dispersion Time of Random Walks on Finite Graphs.

When: April 28, 14:30 hrs (Chilean time).

Link: https://zoom.us/j/91342046761?pwd=bGczR3d6c2Qxdk9sSk1STFVyY2tkZz09

Abstract: Consider two random processes on an n vertex graph related to Internal Diffusion-Limited Aggregation (IDLA). In each process n particles perform independent random walks from a fixed vertex until they reach an unvisited vertex, at which point they settle. In the first process only one particle moves until settling and then the next starts, in the second process all particles are released together.

We study the dispersion time which is the time taken for the longest walk to settle. We present a new coupling which allows us to compare dispersion time across the processes. We additionally prove bounds on the dispersion time(s) in terms of more well-studied parameters of random walks such as hitting times and the mixing time.

### April 21 - 2021

Speaker: Felipe Garrido, LAMSADE, Université Paris Dauphine - PSL

Title: Stable matching games

When: April 21, 14:30 hrs (Chilean time).

Link: https://zoom.us/j/97375770036?pwd=TmxQVjRmRGRTYWFqd2FrcFNFNWdEdz09

Abstract: Gale and Shapley (1962) introduced a matching problem between two sets of agents M and W, who need to be paired by taking into account that each agent on one side of the market has an exogenous preference order over the agents of the other side. They defined a matching as stable if no unmatched pair can both improve their payoffs by breaking their couples and forming a new one. They proved the existence of a stable matching using a deferred-acceptance algorithm. Shapley and Shubik (1971) extended the model by allowing monetary transfers. Our article offers a further extension by assuming that matched couples obtain their payoff endogenously as the outcome of a strategic-form game they have to play. A matching, together with a strategy profile, is externally stable if no unmatched pair can break their couples, form a new one and play a strategy profile in their game such that both of them improve their payoffs. It is internally stable if no agent, by individually changing its strategy inside its couple, can increase its payoff without breaking the external stability of its couple. We prove the existence of an externally and internally stable matching in a large class of problems including zero-sum games, strictly competitive games, potential games and infinitely repeated games. We also prove that our main model encompasses and refines matching with monetary transfers as well as matching with contracts.

### April 14 - 2021

Speaker: Lars Rohwedder, EPFL Lausanne

Title: A (2 + epsilon)-approximation algorithm for preemptive weighted flow time on a single machine.

When: April 14, 14:30 hrs (Chilean time).

Link: https://zoom.us/j/95471087976?pwd=UzFTQVBTRlFNRzNicWk4c0ZGeGZWUT09

Abstract: In a recent breakthrough in scheduling, Batra, Garg, and Kumar gave the first constant approximation algorithm for minimizing the sum of weighted flow times. Wiese and I (STOC'21) managed to improve this large unspecified constant to 2 + epsilon. I will give a very graphic presentation of the algorithmic techniques behind this.

Speaker: Maximilian Janke, TU Munich

Title: Scheduling in the Random-Oder Model

When: March 31, 14:30 hrs (Chilean time).

Link: https://zoom.us/j/95041369607?pwd=amRHU29ZS3AvSHNaQmc4MkdkelBXdz09

Abstract: We study Online Makespan Minimization, one of the most basic scheduling problems, in the random-order model. Here jobs of a given input arrive in a uniformly chosen random order as opposed to the classical adversarial model, which considers worst-case orders. The random-order model originates from the Secretary Problem and has received quite some research interest over the last years.

For scheduling, the random-order model provides beyond worst-case guarantees while still not being overly pessimistic. Furthermore, it leads to a stronger performance measure, which considers 'nearly worst-case' orders. Recent results on Makespan Minimization in the random-order model outperform classical lower bounds, even using this stronger measure. This proves formally that classical worst-case sequences are highly order-reliant and should therefore be rare in practical applications.

In this talk we discuss the role of random-order arrival for Makespan Minimization. We compare recent random-order bounds with various classical online and semi-online guarantees, and introduce key techniques, which allow to profit from random-order arrival. These techniques should be relevant for further research on Random-Order Makespan Minimization and related problems.

This talk is based on the paper Scheduling in the Random-Order Model, which is joint work with Susanne Albers.

Speaker: Sebastián Pérez, Gatech

Title: Adaptive bin packing with overflow

When: March 24, 14:30 hrs (Chilean time).

Link: https://zoom.us/j/95041369607?pwd=amRHU29ZS3AvSHNaQmc4MkdkelBXdz09

Abstract: Motivated by the allocation of virtual machines into servers in the cloud, we consider the online problem of packing items with random sizes into unit-capacity bins. Items arrive sequentially, but upon arrival an item’s actual size is unknown; only its probabilistic information is available to the decision maker. Without knowing this size, the decision maker must irrevocably pack the item into an available bin or place it in a new bin. Once packed in a bin, the decision maker observes the item’s actual size, and overflowing the bin is a possibility. An overflow incurs a large penalty cost and the corresponding bin is unusable for the rest of the process. In practical terms, this overflow models delayed services, failure of servers, and/or loss of end-user goodwill. The objective is to minimize the total expected cost given by the sum of the number of opened bins and the overflow penalty cost. In this talk, we present an online algorithm with expected cost at most a constant factor times the cost incurred by the optimal packing policy when item sizes are drawn from an i.i.d. sequence. We discuss the limits of our approach and extensions to offline settings, where distributions are known in advance but packed sequentially. Joint work with Mohit Singh and Alejandro Toriello.

Speaker: Sabine Limbourg, University of Liege

Title: City logistics and smart delivery

When: March 17, 14:30 hrs (Chilean time).

Link: https://zoom.us/j/92175923247?pwd=QWlhZGpDUUVQSlBFbnNxZk5NNXlPdz09

Abstract: The current and expected growing number of people living and working in cities and the limited space available inside city centres implies a greater exchange of inbound and outbound freight flows between city centres and their surrounding regions. Urban freight transports provide economic benefits to society but are also responsible for negative externalities such as congestion, air and water pollution, climate change, accidents and noise. Access restrictions are one of the most applied measures to control urban traffics in the city's specific areas. A growing use of urban trucks based on electric, hydrogen and hybrid technologies or non-motorized transport such as bikes reduces pollutant emissions, noise and road congestion by making night deliveries and avoiding morning and afternoon peak periods.

This seminar's objective is to discuss how to efficiently distribute shipments to customers from several cities by a freight transport operator. This delivery company has several vehicles to carry products to customers or small depots located at different cities' points. We consider the whole distribution network, allowing us to make decisions at firm, delivering companies and small depots level (Aguayo et al., 2020).

Then we consider a platform bringing together several freight transport operators. Freight bundling is a central characteristic of the systems in focus. Besides, pricing decisions can be simultaneously integrated by extending a bilevel programming formulation (Tawk and Limbourg, 2019). Finally, Unmanned Aerial Vehicle, which is also known as a drone, is examined as a possible way to facilitate biomedical transportation. We deal with the drone network design problem for biomedical material transportation. Four location models are developed and applied to Brussels and its periphery with respect to the associated market in terms of biomedical product flows. In the context of separate case studies of scenario-based analysis, the experiments show that charging stations is useful for extending the mission ranges and gaining market share. The results also show the possibility of gradually implementing the bases without requiring any signifficant changes, such as closing a base (Dhote and Limbourg, 2020).

Acknowledgments

This work was supported by Wallonie-Bruxelles International.

Speaker: Chun-Hung Liu, Texas A&M University

Title: Well-quasi-ordering digraphs by the strong immersion relation

When: Wednesday, December 16, 15:00 hrs (Chilean time).

Link: https://zoom.us/j/97493917037?pwd=YkN0NkhJRHNhMXJOM0NWS3ViY0R1Zz09

Abstract: A well-quasi-ordering is a reflexive and transitive binary relation such that every infinite sequence has a non-trivial increasing subsequence. The study of well-quasi-ordering was stimulated by two conjectures of Vazsonyi in 1940s: trees and subcubic graphs are well-quasi-ordered by the topological minor relation. It is known that the topological minor relation does not well-quasi-order all graphs. Nash-Williams in 1960s introduced the notion of strong immersion and conjectured that the strong immersion relation well-quasi-orders all graphs, which is a common generalization of both conjectures of Vazsonyi. In this talk we consider strong immersion on digraphs. Paths that change direction arbitrarily many times form an infinite antichain with respect to the strong immersion relation. In this talk, we will prove that it is the only obstruction. Namely, for any integer k, digraphs with no paths that change direction at least k times are well-quasi-ordered by the strong immersion relation. Joint work with Irene Muzi.

Speaker: Gwen McKinley, UC San Diego

Title: Counting integer partitions with the method of maximum entropy

When: Wednesday, December 2, 15:00 hrs (Chilean time).

Link: https://zoom.us/j/98543137164?pwd=M1lUaUNPcm1LcnFocEZhRXMvWDRKQT09

Abstract: The problem of asymptotically counting integer partitions has a long and storied history, beginning with the pioneering work of Hardy and Ramanujan in 1918. In the work presented here, we give a probabilistic perspective on this problem, and use this approach to prove an asymptotic formula for the number of partitions of an integer n where the sums of the kth powers of the parts are also fixed, for some collection of values k. To obtain this result, we reframe the counting problem as an optimization problem, and find the probability distribution on the set of all integer partitions with maximum entropy among those that satisfy our restrictions in expectation (in essence, this is an application of Jaynes' principle of maximum entropy). This approach leads to an approximate version of our formula as the solution to a relatively straightforward optimization problem over real-valued functions. To establish more precise asymptotics, we prove a local central limit theorem.

A large portion of the talk will be devoted to outlining how our method can be used to re-derive a classical result of Hardy and Ramanujan, with an emphasis on the intuitions behind the method, and limited technical detail. This is joint work with Marcus Michelen and Will Perkins

### December 2 - 2020

Speaker: José Samper, Pontificia Universidad Católica

Title: Matroids, polymatroids and submodular functions: algebra or optimization?

When: Wednesday, December 2, 14:30 hrs (Chilean time).

Link: https://zoom.us/j/98780890672?pwd=VXpjdEM0Zk9KNWxBcDdKeFlsaEFnUT09

Abstract: Matroids, polymatroids and submodular functions are beautiful objects that have appeared in many areas of mathematics including algebra, geometry, topology and optimization. Consequently, they have been studied from multiple points of view. This oftentimes has the consequence that the same results are proven from different points of view and by very different communities. A notable example being their study in optimization and algebraic combinatorics. The goal of this talk is to tell this story, show how a small mixture of ideas from different communities lead to powerful algebraic tools, and speculate a little a bit about the opposite direction.

### November 25 - 2020

Speaker: Santiago Armstrong, Pontificia Universidad Católica

Title: An optimal algorithm for strict circular seriation.

When: Wednesday November 25, 14:30 hrs (Chilean time).

Link: https://zoom.us/j/91348424630?pwd=eSsvdEhlRU1EeXlWc0RxUnp1TjFKUT09

Abstract: Seriation is an exploratory combinatorial data analysis technique to reorder objects into a sequence along a one-dimensional continuum when the only available information among the objects is their pairwise similarity (or dissimilarity). Linear seriation aims at inferring an ordering (permutation) consistent with an underlying linear order of the data. In many cases however, the data objects may be arranged around a closed continuum yielding a rather circular underlying order. In a matrix representation, this can be visualized as a symmetric matrix of pairwise dissimilarities between objects where elements of each row/column increase monotonically while moving to the right/bottom until some specific element and then decrease again monotonically until the end of each row/column and fold back from the left/top of the matrix. Many approaches used in linear seriation algorithms involve computing the ball hypergraph associated to the dissimilarity. We show that a similar approach can be used in the circular case. In addition to the previous we present an optimal algorithm for strict seriation, which is a natural setting for continuous data.

### November 18 - 2020

Speaker: Victor Verdugo, Universida de O'Higgins

Title: Apportionment Mechanisms under Parity Constraints and the case of Chile and a new Political Constitution.

When: Wednesday November 18, 14:30 hrs (Chilean time).

Link: https://zoom.us/j/93139273671?pwd=VWE1NEplWjRsWFJxSnRnNVVRMlZEUT09

Abstract: How many seats should be allocated to each political party in an election? This question has a long and rich history, and plays a fundamental role in order to ensure appropriate levels of representation in the parliaments. We consider this question in the presence of types (e.g. men and women), where apart from ensuring proportionality at the party level, we also have to find an allocation which is paritary for the types. We consider two different approaches: one of them, with a greedy/local search paradigm, corresponds to a mechanism recently approved in the chilean parliament (March 2020) to find the representatives of the constitutional assembly with the goal of designing a new political constitution for Chile (election to happen in April 2021); the other one is based on the idea of integral biproportionality, introduced by Balinski and Demange in the late 80’s. We analyze both mechanisms from an axiomatic and quantitative point of view. We also provide new results regarding integral biproportional solutions and the fair share, a.k.a matrix scaling solution, which represents the ideal (but not necessarily implementable) fractional biproportional solution.

Joint work with Claire Mathieu (CNRS & IRIF, France)

Speaker: Arturo Merino, TU-Berlin

Title: On the two-dimensional knapsack problem for convex polygons.

When: Wednesday October 28, 14:30 hrs (Chilean time).

Link: https://zoom.us/j/95413798884?pwd=ait4K0J4WHFSZTVVMXdJN1VFVGFyZz09

Abstract: We study the two-dimensional geometric knapsack problem for convex polygons. Given a set of weighted convex polygons and a square knapsack, the goal is to select the most profitable subset of the given polygons that fits non-overlappingly into the knapsack. We allow rotating the polygons by arbitrary angles.

In this talk we will first present:

- a quasi-poly time O(1)-approximation

- a poly time O(1)-approximation algorithm if all input polygons are triangles.

We will then look into the setting of resource augmentation, i.e., we allow to increase the size of the knapsack by a factor of 1 + δ for some δ > 0 but compare ourselves with the optimal solution for the original knapsack. In the resource augmentation setting we present:

- a poly time O(1)-approximation

- a quasi-poly time algorithm that computes a solution of optimal weight.

To the best of our knowledge, these are the first results for two-dimensional geometric knapsack in which the input objects are more general than axis-parallel rectangles or circles and in which the input polygons can be rotated by arbitrary angles.

This is joint work with Andreas Wiese.

Speaker: Francisco Marmolejo, University of Oxford and IOHK.

Title: Strategic and Structural Aspects of Bitcoin Mining

When: Wednesday October 21, 14:30 hrs (Chilean time).

Link: https://zoom.us/j/92034905790?pwd=RjFlL29iQzIwQ1hkSnQrdG1uOTVXUT09

Abstract:Just over a decade ago, Satoshi Nakamoto published a landmark white paper outlining the backbone protocol to Bitcoin, arguably the world's first mainstream digital currency. Through the Nakamoto protocol and blockchain technology, users can reliably agree upon a common transaction history maintained by miners on the public Bitcoin ledger in a decentralised and anonymous fashion. This is possible in part because agents within the protocol are assumed to be strategic rather than adversarial---a fair assumption when creating a ledger for currency. The Nakamoto protocol is thus at its core a decentralised consensus protocol among strategic agents that is built from cryptographic primitives and judicious incentive engineering. In this talk I will give an overview of how game theory is an important tool to understand decentralised consensus protocols such as Bitcoin. Along the way, I will highlight recent work pertaining to strategic mining within "pools" of miners and inherent structural limitations of Bitcoin-like proof-of-work (PoW) consensus protocols.

### October 07 - 2020

Speaker: Santiago R. Balseiro, Columbia University.

Title: Dynamic Pricing of Relocating Resources in Large Networks

When: Wednesday October 07, 14:30 hrs (Chile time).

Link: https://zoom.us/j/96968142246?pwd=c1BleFZ3S0F3WXA1b1RGdGlYYWVRQT09

Abstract: Motivated by applications in shared vehicle systems, we study dynamic pricing of resources that relocate over a network of locations. Customers with private willingness-to-pay sequentially request to relocate a resource from one location to another, and a revenue-maximizing service provider sets a price for each request. This problem can be formulated as an infinite horizon stochastic dynamic program, but is quite difficult to solve, as optimal pricing policies may depend on the locations of all resources in the network. We first focus on networks with a hub-and-spoke structure, and we develop a dynamic pricing policy and a performance bound based on a Lagrangian relaxation. This relaxation decomposes the problem over spokes and is thus far easier to solve than the original problem. We analyze the performance of the Lagrangian-based policy and focus on a supply-constrained large network regime in which the number of spokes ($n$) and the number of resources grow at the same rate. We show that the Lagrangian policy loses no more than $O(\sqrt{\ln(n)/n})$ in performance compared to an optimal policy, thus implying asymptotic optimality as $n$ grows large. We also show that no static policy is asymptotically optimal in the large network regime. Finally, we extend the Lagrangian relaxation to provide upper bounds and policies to general networks with multiple, interconnected hubs and spoke-to-spoke connections, and to incorporate relocation times. We also examine the performance of the Lagrangian policy and the Lagrangian relaxation bound on some numerical examples, including examples based on data from RideAustin.

Joint work with David B. Brown (Duke University) and Chen Chen (University of Chicago).

Paper: https://ssrn.com/abstract=3313737

### September 23 - 2020

Speaker: Benjamin Moseley, Carnegie Mellon University.

When: Wednesday 23 de Septiembre, 14:30 hrs (Chile time).

Abstract: Combinatorial optimization often focuses on optimizing for the worst-case. However, the best algorithm to use depends on the "relative inputs", which is application specific and often does not have a formal definition.

The talk gives a new theoretical model for designing algorithms that are tailored to inputs for the application at hand. In the model, learning is performed on past problem instances to make predictions on future instances. These predictions are incorporated into the design and analysis of the algorithm. The predictions can be used to achieve "instance-optimal" algorithm design when the predictions are accurate and the algorithm's performance gracefully degrades when there is error in the prediction.

The talk will apply this framework to applications in online algorithm design and give algorithms with theoretical performance that goes beyond worst-case analysis. The majority of the talk will focus on load balancing on unrelated machines.

Speaker: Nicolas Stier-Moses, Co-Director de Facebook Core Data Science.

Title: Pacing Mechanisms For Ad Auctions

When: Wednesday September 30, 14:30 hrs (Chile time).

Abstract: Budgets play a significant role in real-world sequential auction markets such as those implemented by Internet companies. To maximize the value provided to auction participants, spending is smoothed across auctions so budgets are used for the best opportunities. Motivated by pacing mechanisms used in practice by online ad auction platforms, we discuss smoothing procedures that ensure that campaign daily budgets are consistent with maximum bids. Reinterpreting this process as a game between bidders, we introduce the notion of pacing equilibrium, and study properties such as existence, uniqueness, complexity and efficiency, both for the case of second and first price auctions. In addition, we connect these equilibria to more general notions of market equilibria, and study how compact representations of a market lead to more efficient approaches to compute approximate equilibria.

Papers:

Second price pacing: https://arxiv.org/abs/1706.07151

First price pacing: https://arxiv.org/abs/1811.07166

Abstractions: https://arxiv.org/abs/1901.06230