No sublogarithmic-time approximation scheme for bipartite vertex cover

DOI10.1007/s00446-013-0194-zzbMath1320.68224OpenAlexW3104625252MaRDI QIDQ2256970

Mika Göös, Jukka Suomela

Publication date: 23 February 2015

Published in: Distributed Computing (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/10138/37521

zbMATH Keywords

lower boundsvertex coverlocal approximationdistributed graph algorithms

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Randomized algorithms (68W20) Distributed algorithms (68W15)

Related Items

The Complexity of Distributed Approximation of Packing and Covering Integer Linear Programs ⋮ A Time Hierarchy Theorem for the LOCAL Model

Cites Work

• Unnamed Item
• Unnamed Item
• Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
• Low diameter graph decompositions
• Existence and explicit constructions of \(q+1\) regular Ramanujan graphs for every prime power \(q\)
• Survey of local algorithms
• Lower bounds for local approximation
• Local Computation
• Expander graphs and their applications
• Fast Distributed Approximations in Planar Graphs
• Leveraging Linial’s Locality Limit
• The price of being near-sighted
• A Local 2-Approximation Algorithm for the Vertex Cover Problem
• Locality in Distributed Graph Algorithms
• Distributed Computing: A Locality-Sensitive Approach
• Large deviations for sums of partly dependent random variables
• What Can be Computed Locally?
• No Sublogarithmic-Time Approximation Scheme for Bipartite Vertex Cover
• Local Graph Partitions for Approximation and Testing
• What cannot be computed locally!