Publication

Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover

Publications associées (40)

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Connectez-vous pour utiliser Chat avec Graph Search

Results on Sparse Integer Programming and Geometric Independent Sets

Jana Tabea Cslovjecsek

An integer linear program is a problem of the form max{c^T x : Ax=b, x >= 0, x integer}, where A is in Z^(n x m), b in Z^m, and c in Z^n.Solving an integer linear program is NP-hard in general, but there are several assumptions for which it becomes fixed p ...

EPFL2023

Consider the family of bounded degree graphs in any minor-closed family (such as planar graphs). Let d be the degree bound and n be the number of vertices of such a graph. Graphs in these classes have hyperfinite decompositions, where, one removes a small ...

IEEE COMPUTER SOC2022

Space-Efficient Representations of Graphs

Jakab Tardos

With the increasing prevalence of massive datasets, it becomes important to design algorithmic techniques for dealing with scenarios where the input to be processed does not fit in the memory of a single machine. Many highly successful approaches have emer ...

EPFL2022

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

EPFL2021

Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samples

Mikhail Kapralov, Slobodan Mitrovic, Ashkan Norouzi Fard, Jakab Tardos

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

ASSOC COMPUTING MACHINERY2020

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

Dynamic Balanced Graph Partitioning

Andreas Loukas

This paper initiates the study of the classic balanced graph partitioning problem from an online perspective: Given an arbitrary sequence of pairwise communication requests between n nodes, with patterns that may change over time, the objective is to servi ...

2020

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

No Small Linear Program Approximates Vertex Cover Within a Factor 2-epsilon

Ola Nils Anders Svensson, Abbas Bazzi

The vertex cover problem is one of the most important and intensively studied combinatorial optimization problems. Khot and Regev [Khot S, Regev O (2008) Vertex cover might be hard to approximate to within 2 - epsilon. J. Comput. System Sci. 74(3): 335-349 ...

INFORMS2019

Approximating the rectilinear crossing number

János Pach

A straight-line drawing of a graph G is a mapping which assigns to each vertex a point in the plane and to each edge a straight-line segment connecting the corresponding two points. The rectilinear crossing number of a graph G, (cr) over bar (G), is the mi ...

2019