**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Publication# How to Match in Modern Computational Settings

Abstract

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 algorithm only knows the distribution from which the edges are sampled.In the query-commit model, the algorithm must query edges to know if they exist and is committed to adding all queried edges that exist to its output.In the price-of-information model, the algorithm incurs costs for querying edges, and the total query cost is subtracted from the output matching's weight.For maximum weighted matching in these models, previously known best algorithms were greedy algorithms that achieve 1/2 approximations. We improve the approximation ratio to 1 - 1/e in both models. Next, we consider situations where the input graphs do not fit into the space available for an algorithm instance. We consider two such models: the semi-streaming model where the algorithm receives the input as a stream of edges and the algorithm has only sub-linear (in the number of edges) space, and the massively parallel computation (MPC) model where the input is distributed among several machines, each of which has sub-linear space, and algorithm instances running on different machines must communicate in synchronous rounds.We start with a particular case of the semi-streaming model where the edges arrive in uniformly random order, and the algorithm goes over the stream only once. For this setting, we give the first algorithm that finds a (1/2 + c)-approximate maximum weighted matching in expectation; such algorithms were previously known only for the unweighted graphs.We then show how to efficiently find (1 - epsilon)-approximate weighted matchings for any epsilon > 0 in multi-pass semi-streaming and MPC models by extending our algorithmic ideas used in the single-pass semi-streaming model with random order edge arrivals.Finally, we study online algorithms for matching, where the input graph is gradually revealed over time. In the online edge-arrival setting, the graph is revealed one edge at a time, and an algorithm is forced to make irrevocable decisions on whether to add each edge to the output matching upon their arrival. We show that no online algorithm can achieve a competitive ratio of 1/2 + c for any constant c > 0 in this setting.In the online vertex-arrival setting, the graph is revealed one vertex at a time, together with its incident edges to already revealed vertices, and the algorithm must irrevocably decide to ignore the revealed vertex or match it to one of the available neighbors.In this setting, we show how to round a previously known fractional online matching algorithm to get an integral online matching algorithm with a competitive ratio of 1/2 + c for some constant c > 0.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related MOOCs (27)

Related publications (9)

Related concepts (26)

IoT Systems and Industrial Applications with Design Thinking

The first MOOC to provide a comprehensive introduction to Internet of Things (IoT) including the fundamental business aspects needed to define IoT related products.

Selected Topics on Discrete Choice

Discrete choice models are used extensively in many disciplines where it is important to predict human behavior at a disaggregate level. This course is a follow up of the online course “Introduction t

Selected Topics on Discrete Choice

Discrete choice models are used extensively in many disciplines where it is important to predict human behavior at a disaggregate level. This course is a follow up of the online course “Introduction t

Algorithm

In mathematics and computer science, an algorithm (ˈælɡərɪðəm) is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing calculations and data processing. More advanced algorithms can use conditionals to divert the code execution through various routes (referred to as automated decision-making) and deduce valid inferences (referred to as automated reasoning), achieving automation eventually.

Parallel computing

Parallel computing is a type of computation in which many calculations or processes are carried out simultaneously. Large problems can often be divided into smaller ones, which can then be solved at the same time. There are several different forms of parallel computing: bit-level, instruction-level, data, and task parallelism. Parallelism has long been employed in high-performance computing, but has gained broader interest due to the physical constraints preventing frequency scaling.

Approximation

An approximation is anything that is intentionally similar but not exactly equal to something else. The word approximation is derived from Latin approximatus, from proximus meaning very near and the prefix ad- (ad- before p becomes ap- by assimilation) meaning to. Words like approximate, approximately and approximation are used especially in technical or scientific contexts. In everyday English, words such as roughly or around are used with a similar meaning. It is often found abbreviated as approx.

This thesis focuses on designing spectral tools for graph clustering in sublinear time. With the emergence of big data, many traditional polynomial time, and even linear time algorithms have become pr

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

Ola Nils Anders Svensson, Mikhail Kapralov, Andreas Maggiori, Buddhima Ruwanmini Gamlath Gamlath Ralalage, 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 o