Online Matching with General Arrivals

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

We develop an algorithm to solve the bottleneck assignment problem (BAP) that is amenable to having computation distributed over a network of agents. This consists of exploring how each component of the algorithm can be distributed, with a focus on one com ...

This work aims to study the effects of wind uncertainties in civil engineering structural design. Optimising the design of a structure for safety or operability without factoring in these uncertainties can result in a design that is not robust to these per ...

This thesis focuses on the maximum matching problem in modern computational settings where the algorithms have to make decisions with partial information. First, we consider two stochastic models called query-commit and price-of-information where the algo ...

One of the most basic graph problems, All-Pairs Shortest Paths (APSP) is known to be solvable in n^{3-o(1)} time, and it is widely open whether it has an O(n^{3-ε}) time algorithm for ε > 0. To better understand APSP, one often strives to obtain subcubic t ...

This paper examines the binning of two types of parts with random characteristics, so that a componentwise monotonic evaluation criterion exhibits a minimum deviation to a given target value over all possible realizations. The optimal matching classes are ...

Several discrete geometry problems are equivalent to estimating the size of the largest homogeneous sets in graphs that happen to be the union of few comparability graphs. An important observation for such results is that if G is an n-vertex graph that is ...

Let c denote the largest constant such that every C-6-free graph G contains a bipartite and C-4-free subgraph having a fraction c of edges of G. Gyori, Kensell and Tompkins showed that 3/8

Given a source of iid samples of edges of an input graph G with n vertices and m edges, how many samples does one need to compute a constant factor approximation to the maximum matching size in G? Moreover, is it possible to obtain such an estimate in a sm ...

We study different symbolic algorithms to solve two related reconfiguration problems on graphs: the token swapping problem and the permutation routing via matchings problem. Input to both problems is a connected graph with labeled vertices and a token in e ...

In this thesis we give new algorithms for two fundamental graph problems. We develop novel ways of using linear programming formulations, even exponential-sized ones, to extract structure from problem instances and to guide algorithms in making progress. S ...

Vizing's celebrated theorem asserts that any graph of maximum degree Delta admits an edge coloring using at most Delta + 1 colors. In contrast, Bar-Noy, Motwani and Naor showed over a quarter century ago that the trivial greedy algorithm, which uses 2 Delt ...

Graph alignment in two correlated random graphs refers to the task of identifying the correspondence between vertex sets of the graphs. Recent results have characterized the exact information-theoretic threshold for graph alignment in correlated Erdös-Rény ...

We design a generic method to reduce the task of finding weighted matchings to that of finding short augmenting paths in unweighted graphs. This method enables us to provide efficient implementations for approximating weighted matchings in the massively pa ...

Consider the problem of constructing a polar code of block length N for a given transmission channel W. Previous approaches require one to compute the reliability of the N synthetic channels and then use only those that are sufficiently reliable. However, ...

Given two graphs H and F, the maximum possible number of copies of H in an F-free graph on n vertices is denoted by ex(n, H, F). We investigate the function ex(n, H, kF), where kF denotes k vertex disjoint copies of a fixed graph F. Our results include cas ...

We consider the problem of estimating the value of MAX-CUT in a graph in the streaming model of computation. At one extreme, there is a trivial 2-approximation for this problem that uses only O(log n) space, namely, count the number of edges and output hal ...

Data-driven modeling and feedback control play a vital role in several application areas ranging from robotics, control theory, manufacturing to management of assets, financial portfolios and supply chains. Many such problems in one way or another are rela ...

This paper studies sufficient conditions to obtain efficient distributed algorithms coloring graphs optimally (i.e. with the minimum number of colors) in the LOCAL model of computation. Most of the work on distributed vertex coloring so far has focused on ...

Online Matching with General Arrivals

Chat with Graph Search

A Distributed Augmenting Path Approach for the Bottleneck Assignment Problem

Multi-Level Monte Carlo Methods for Uncertainty Quantification and Risk-Averse Optimisation

How to Match in Modern Computational Settings

Faster Monotone Min-Plus Product, Range Mode, and Single Source Replacement Paths

Minimum-Error Classes for Matching Parts

Improved Ramsey-type results for comparability graphs

On subgraphs of C-2k-free graphs and a problem of Kuhn and Osthus

Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samples

Symbolic Algorithms for Token Swapping

New Graph Algorithms via Polyhedral Techniques

Tight Bounds for Online Edge Coloring

Analysis of a Canonical Labeling Algorithm for the Alignment of Correlated Erdős-Rényi Graphs

Weighted Matchings via Unweighted Augmentations

Construction of Polar Codes With Sublinear Complexity

Generalized Turan problems for disjoint copies of graphs

Ordered Graphs And Large Bi-Cliques In Intersection Graphs Of Curves

Ordered graphs and large bi-cliques in intersection graphs of curves

An Optimal Space Lower Bound for Approximating MAX-CUT

Kernel methods and Model predictive approaches for Learning and Control

Distributed Coloring of Graphs with an Optimal Number of Colors