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

Future events

May 25- 2022

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.

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.

Stijn Cambie.mp4

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.

Yuri Faenza.mp4

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.

Raimundo_SaonaGMT20210609-183458_Recording_1920x1080.mp4

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.

Ulrike Schmidt-Kraepelin.mp4

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.

Waldo- Galvez-GMT20210512-183541_Recording_1920x1080.mp4

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

zoom_0.mp4

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.

zoom_1.mp4

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.

zoom_0.mp4

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.

zoom_0.mp4

March 31 - 2021 [paper]

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.

zoom_0.mp4

March 24 - 2021 [paper]

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.

zoom_0.mp4

March 15 - 2021 [article]

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.



December 16 - 2020 [slides]

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.


December 9 - 2020 [slides]

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


GwenMcKinley09-12-20.mp4

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.

JoseSampers02-12-20.mp4

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.

SantiagoArmstrong-25-11.mp4

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)

VictorVerdugo18-11-20.mp4

October 28 - 2020 [slides]

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.


zoom_0-00.00.00.000-00.44.20.788.mp4

October 21 - 2020 [slides]

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.

zoom_1.mp4

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


SantiagoBalseiro-07-10-20.mp4

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.

September 30 - 2020 [slides]

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