Borel oracles. An analytical approach to constant-time algorithms

DOI10.1090/S0002-9939-10-10291-3zbMATH Open1200.68283arXiv0907.1805OpenAlexW2117195616MaRDI QIDQ3581114FDOQ3581114

Authors: Gábor Elek, Gabor Lippner 

Publication date: 16 August 2010

Published in: Proceedings of the American Mathematical Society (Search for Journal in Brave)

Abstract: Nguyen and Onak constructed the first constant-time algorithm for the approximation of the size of the maximum matching in bounded degree graphs. The Borel oracle machinery is a tool that can be used to convert some statements in Borel graph theory to theorems in the field of constant-time algorithms. In this paper we illustrate the power of this tool to prove the existence of the above mentioned constant-time approximation algorithm.

Full work available at URL: https://arxiv.org/abs/0907.1805

Recommendations

• Improved constant-time approximation algorithms for maximum matchings and other optimization problems
• An improved constant-time approximation algorithm for maximum~matchings
• An efficient partitioning oracle for bounded-treewidth graphs
• On constant time approximation of parameters of bounded degree graphs
• Constant-time local computation algorithms

zbMATH Keywords

invariant measuresgraph limitsmaximum matchingBorel graphsconstant-time algorithms

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Descriptive set theory (03E15)

Cites Work

• Recurrence of distributional limits of finite planar graphs
• Topics in orbit equivalence
• Processes on unimodular random networks
• Title not available (Why is that?)
• Title not available (Why is that?)
• Borel chromatic numbers
• Closed Sets Without Measurable Matching
• Parameter testing in bounded degree graphs of subexponential growth

Cited In (23)

• Measurable equidecompositions for group actions with an expansion property
• Matchings on infinite graphs
• Kőnig's line coloring and Vizing's theorems for graphings
• Measurable versions of Vizing's theorem
• Approximate Schreier decorations and approximate Kőnig's line coloring theorem
• Orienting Borel graphs
• Controllability, matching ratio and graph convergence
• Følner tilings for actions of amenable groups
• Tilings in graphons
• Lower matching conjecture, and a new proof of Schrijver's and Gurvits's theorems
• Suboptimality of local algorithms for a class of max-cut problems
• Matchings in Benjamini-Schramm convergent graph sequences
• Ramanujan graphings and correlation decay in local algorithms
• Factor of iid percolation on trees
• Ultraproducts of measure preserving actions and graph combinatorics
• Matchings on trees and the adjacency matrix: A determinantal viewpoint
• Approximating Cayley diagrams versus Cayley graphs
• On Baire measurable colorings of group actions
• Perfect matchings as IID factors on non-amenable groups
• Spectral measures of factor of i.i.d. processes on vertex-transitive graphs
• Matching measure, Benjamini-Schramm convergence and the monomer-dimer free energy
• A determinacy approach to Borel combinatorics
• Limits of locally-globally convergent graph sequences

This page was built for publication: Borel oracles. An analytical approach to constant-time algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3581114)