Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover
 
conference paper

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

Ghaffari, Mohsen
•
Gouleakis, Themis
•
Konrad, Christian
Show more
January 1, 2018
Podc'18: Proceedings Of The 2018 Acm Symposium On Principles Of Distributed Computing
37th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC)

We present O(log log n)-round algorithms in the Massively Parallel Computation (MPC) model, with a(n) memory per machine, that compute a maximal independent set, a 1 + epsilon approximation of maximum matching, and a 2 + epsilon approximation of minimum vertex cover, for any n-vertex graph and any constant epsilon > 0. These improve the state of the art as follows: Our MIS algorithm leads to a simple O(log log A)-round MIS algorithm in the CONGESTED-CLIQUE model of distributed computing, which improves on the (O) over tilde(root log Delta)-round algorithm of Ghaffari [PODC'17]. Our O(log log(2) n)-round (1 + epsilon)-approximate maximum matching algorithm simplifies or improves on the following prior work: O(log2 log n)-round (1 + epsilon)-approximation algorithm of Czumaj et al. [STOC'18] and O(log log n)-round (1 + epsilon) approximation algorithm of Assadi et al. [arXiv'17]. Our O(log log n)-round (2 + epsilon)-approximate minimum vertex cover algorithm improves on an O(log log n)-round O(1)-approximation of Assadi et al. [arXiv'17].

  • Details
  • Metrics
Type
conference paper
DOI
10.1145/3212734.3212743
Web of Science ID

WOS:000458186900016

Author(s)
Ghaffari, Mohsen
Gouleakis, Themis
Konrad, Christian
Mitrovic, Slobodan
Rubinfeld, Ronitt
Date Issued

2018-01-01

Publisher

ASSOC COMPUTING MACHINERY

Publisher place

New York

Published in
Podc'18: Proceedings Of The 2018 Acm Symposium On Principles Of Distributed Computing
ISBN of the book

978-1-4503-5795-1

Start page

129

End page

138

Subjects

Computer Science, Hardware & Architecture

•

Computer Science, Theory & Methods

•

Engineering, Electrical & Electronic

•

Computer Science

•

Engineering

•

maximal independent set

•

maximum matching

•

vertex cover

•

massively parallel computation

•

congested clique

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
MATH  
Event nameEvent placeEvent date
37th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC)

Egham, ENGLAND

Jul 23-27, 2018

Available on Infoscience
June 18, 2019
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/156872
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés