Publication

A Distributed Augmenting Path Approach for the Bottleneck Assignment Problem

Publications associées (28)

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

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

EPFL2023

How to Match in Modern Computational Settings

Buddhima Ruwanmini Gamlath Gamlath Ralalage

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

EPFL2021

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

Daniel Keller, Andrii Stepaniuk

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

HUMANA PRESS INC2022

Improved Ramsey-type results for comparability graphs

Istvan Tomon, Dániel József Korándi

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

CAMBRIDGE UNIV PRESS2020

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

Abhishek Methuku

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

2020

Materials Cloud, a platform for open computational science

Sebastiaan Philippe Huber, Nicola Marzari, Fernando Gargiulo, Giovanni Pizzi, Aliaksandr Yakutovich, Berend Smit, Martin Uhrin, Snehal Pramod Kumbhar, Spyros Zoupanos, Christoph Leopold Talirz, Elsa Passaro, Casper Welzel Andersen, Daniele Passerone

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

2020

Symbolic Algorithms for Token Swapping

Giovanni De Micheli, Mathias Soeken, Bruno Schmitt Antunes

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

2020

Weighted Matchings via Unweighted Augmentations

Slobodan Mitrovic, Ola Nils Anders Svensson, Buddhima Ruwanmini Gamlath Gamlath Ralalage

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

ASSOC COMPUTING MACHINERY2019

Construction of Polar Codes With Sublinear Complexity

Rüdiger Urbanke, Seyed Hamed Hassani, Marco Mondelli

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

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2019

New Graph Algorithms via Polyhedral Techniques

Jakub Tarnawski

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

EPFL2019

Tight Bounds for Online Edge Coloring

David Wajc

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

IEEE COMPUTER SOC2019

Generalized Turan problems for disjoint copies of graphs

Abhishek Methuku

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

Elsevier2019

Online Matching with General Arrivals

Mikhail Kapralov, Ola Nils Anders Svensson, Buddhima Ruwanmini Gamlath Gamlath Ralalage, Andreas Maggiori, David Wajc

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

IEEE COMPUTER SOC2019

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

Matthias Grossglauser, Osman Emre Dai, Negar Kiyavash

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

Association for Computing Machinery (ACM)2019

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

János Pach, Istvan Tomon

An ordered graph G(

COMENIUS UNIV2019

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

János Pach, Istvan Tomon

An ordered graph G(

ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD2019

Anytime Heuristic for Weighted Matching Through Altruism-Inspired Behavior

Boi Faltings, Panayiotis Danassis, Aris Filos Ratsikas

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

2019

Integration of ecosystem services in regional spatial plans in Western Switzerland

Jérôme Chenal, Rémi Jaligot

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

2019

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

Patrick Jermann, Francisco Pereira Correia Pinto, Roland John Tormey, Cécile Hardebolle

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

2019

Finding Perfect Matchings in Bipartite Hypergraphs

Chidambaram Annamalai

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

SPRINGER HEIDELBERG2018