A Distributed Augmenting Path Approach for the Bottleneck Assignment Problem

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.

Agent-based simulations have been widely applied in many disciplines, by scientists and engineers alike. Scientists use agent-based simulations to tackle global problems, including alleviating poverty, reducing violence, and predicting the impact of pandem ...

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

Neuroscience incorporates knowledge from a range of scales, from single molecules to brain wide neural networks. Modeling is a valuable tool in understanding processes at a single scale or the interactions between two adjacent scales and researchers use a ...

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

Materials Cloud is a platform designed to enable open and seamless sharing of resources for computational science, driven by applications in materials modelling. It hosts (1) archival and dissemination services for raw and curated data, together with their ...

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

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

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

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

The online matching problem was introduced by Karp, Vazirani and Vazirani nearly three decades ago. In that seminal work, they studied this problem in bipartite graphs with vertices arriving only on one side, and presented optimal deterministic and randomi ...

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 present a novel anytime heuristic (ALMA), inspired by the human principle of altruism, for solving the assignment problem. ALMA is decentralized, completely uncoupled, and requires no communication between the participants. We prove an upper bound on th ...

The concept of ecosystem services (ES) is regarded as an increasingly important framework and tool to support spatial planning. A limited understanding of how ES knowledge is used in spatial plans constrains our ability to learn from, replicate, and convey ...

This paper reports results of the deployment of a learning analytics dashboard in the context of introductory Maths, Physics and Chemistry courses in the first year of the Engineering bachelor of a Swiss technical university. Informed by research on self r ...

Haxell's condition [14] is a natural hypergraph analog of Hall's condition, which is a well-known necessary and sufficient condition for a bipartite graph to admit a perfect matching. That is, when Haxell's condition holds it forces the existence of a perf ...

A Distributed Augmenting Path Approach for the Bottleneck Assignment Problem

Chat with Graph Search

Generalizing Bulk-Synchronous Parallel Processing for Data Science: From Data to Threads and Agent-Based Simulations

How to Match in Modern Computational Settings

A Modular Workflow for Model Building, Analysis, and Parameter Estimation in Systems Biology and Neuroscience

Improved Ramsey-type results for comparability graphs

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

Materials Cloud, a platform for open computational science

Symbolic Algorithms for Token Swapping

Weighted Matchings via Unweighted Augmentations

Construction of Polar Codes With Sublinear Complexity

New Graph Algorithms via Polyhedral Techniques

Tight Bounds for Online Edge Coloring

Generalized Turan problems for disjoint copies of graphs

Online Matching with General Arrivals

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

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

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

Anytime Heuristic for Weighted Matching Through Altruism-Inspired Behavior

Integration of ecosystem services in regional spatial plans in Western Switzerland

Impact of a learning analytics dashboard on the practice of students and teachers

Finding Perfect Matchings in Bipartite Hypergraphs