(1- ϵ )-Approximate Maximum Weighted Matching in poly(1/ ϵ , log n ) Time in the Distributed and Parallel Settings (Q6202220): Difference between revisions

Latest revision as of 17:05, 28 August 2024

scientific article; zbMATH DE number 7824309

Language	Label	Description	Also known as
English	(1- <i>ϵ</i> )-Approximate Maximum Weighted Matching in poly(1/ <i>ϵ</i> , log <i>n</i> ) Time in the Distributed and Parallel Settings	scientific article; zbMATH DE number 7824309

Statements

instance of

scholarly article

0 references

title

(1- ϵ )-Approximate Maximum Weighted Matching in poly(1/ ϵ , log n ) Time in the Distributed and Parallel Settings (English)

0 references

0 references

0 references

Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing

0 references

publication date

26 March 2024

0 references

full work available at URL

https://arxiv.org/abs/2212.14425

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

Distributed Approximate Maximum Matching in the CONGEST Model.

0 references

Linear programming in the semi-streaming model with application to the maximum matching problem

0 references

A fast and simple randomized parallel algorithm for the maximal independent set problem

0 references

Distributed Approximation of Maximum Independent Set and Maximum Matching

0 references

Q4038720

0 references

A simple approximation algorithm for the weighted matching problem

0 references

Connectivity oracles for failure prone graphs

0 references

Linear-Time Approximation for Maximum Weight Matching

0 references

Maximum matching and a polyhedron with 0,1-vertices

0 references

Faster scaling algorithms for general graph matching problems

0 references

Weighted Matchings via Unweighted Augmentations

0 references

Distributed Minimum Cut Approximation

0 references

Deterministic distributed edge-coloring with fewer colors

0 references

Sublinear-Time Parallel Algorithms for Matching and Related Problems

0 references

On the Distributed Complexity of Computing Maximal Matchings

0 references

Approximating weighted matchings in parallel

0 references

A fast and simple randomized parallel algorithm for maximal matching

0 references

Local Computation

0 references

Improved Distributed Approximate Matching

0 references

Distributed Approximate Matching

0 references

A Simple Parallel Algorithm for the Maximal Independent Set Problem

0 references

A simpler linear time \( \frac{2}{3} - \varepsilon\) approximation for maximum weight matching

0 references

Distributed Verification and Hardness of Distributed Approximation

0 references

A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{V}E)\) general graph maximum matching algorithm

0 references

Distributed Weighted Matching

0 references

Identifiers

arXiv ID

2212.14425

0 references

DOI

10.1145/3583668.3594570

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:6202220

@@ Property / cites work @@
+Distributed Approximate Maximum Matching in the CONGEST Model.
+Normal rank
@@ Property / cites work @@
+Linear programming in the semi-streaming model with application to the maximum matching problem
+Normal rank
@@ Property / cites work @@
+A fast and simple randomized parallel algorithm for the maximal independent set problem
+Normal rank
@@ Property / cites work @@
+Distributed Approximation of Maximum Independent Set and Maximum Matching
+Normal rank
@@ Property / cites work @@
+Q4038720
@@ Property / cites work: Q4038720 / rank @@
+Normal rank
@@ Property / cites work @@
+A simple approximation algorithm for the weighted matching problem
+Normal rank
@@ Property / cites work @@
+Connectivity oracles for failure prone graphs
@@ Property / cites work: Connectivity oracles for failure prone graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Linear-Time Approximation for Maximum Weight Matching
+Normal rank
@@ Property / cites work @@
+Maximum matching and a polyhedron with 0,1-vertices
+Normal rank
@@ Property / cites work @@
+Faster scaling algorithms for general graph matching problems
+Normal rank
@@ Property / cites work @@
+Weighted Matchings via Unweighted Augmentations
@@ Property / cites work: Weighted Matchings via Unweighted Augmentations / rank @@
+Normal rank
@@ Property / cites work @@
+Distributed Minimum Cut Approximation
@@ Property / cites work: Distributed Minimum Cut Approximation / rank @@
+Normal rank
@@ Property / cites work @@
+Deterministic distributed edge-coloring with fewer colors
+Normal rank
@@ Property / cites work @@
+Sublinear-Time Parallel Algorithms for Matching and Related Problems
+Normal rank
@@ Property / cites work @@
+On the Distributed Complexity of Computing Maximal Matchings
+Normal rank
@@ Property / cites work @@
+Approximating weighted matchings in parallel
@@ Property / cites work: Approximating weighted matchings in parallel / rank @@
+Normal rank
@@ Property / cites work @@
+A fast and simple randomized parallel algorithm for maximal matching
+Normal rank
@@ Property / cites work @@
+Local Computation
@@ Property / cites work: Local Computation / rank @@
+Normal rank
@@ Property / cites work @@
+Improved Distributed Approximate Matching
@@ Property / cites work: Improved Distributed Approximate Matching / rank @@
+Normal rank
@@ Property / cites work @@
+Distributed Approximate Matching
@@ Property / cites work: Distributed Approximate Matching / rank @@
+Normal rank
@@ Property / cites work @@
+A Simple Parallel Algorithm for the Maximal Independent Set Problem
+Normal rank
@@ Property / cites work @@
+A simpler linear time \( \frac{2}{3} - \varepsilon\) approximation for maximum weight matching
+Normal rank
@@ Property / cites work @@
+Distributed Verification and Hardness of Distributed Approximation
+Normal rank
@@ Property / cites work @@
+A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{V}E)\) general graph maximum matching algorithm
+Normal rank
@@ Property / cites work @@
+Distributed Weighted Matching
@@ Property / cites work: Distributed Weighted Matching / rank @@
+Normal rank

(1- <i>ϵ</i> )-Approximate Maximum Weighted Matching in poly(1/ <i>ϵ</i> , log <i>n</i> ) Time in the Distributed and Parallel Settings (Q6202220): Difference between revisions

Latest revision as of 17:05, 28 August 2024

Statements

Identifiers

Sitelinks

Mathematics(1 entry)