Borel oracles. An analytical approach to constant-time algorithms

DOI10.1090/S0002-9939-10-10291-3MaRDI QIDQ3581114zbMATH OpenOpenAlexFDO

Authors Gábor Elek, Gabor Lippner

Publication date 16 August 2010

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

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 1194938 (Why is no real title available?)
• scientific article; zbMATH DE number 5057523 (Why is no real title available?)
• Borel chromatic numbers
• Closed Sets Without Measurable Matching
• Parameter testing in bounded degree graphs of subexponential growth
• Processes on unimodular random networks
• Recurrence of distributional limits of finite planar graphs
• Topics in orbit equivalence

Cited in

(23)

• Limits of locally-globally convergent graph sequences
• 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
• Controllability, matching ratio and graph convergence
• Orienting Borel graphs
• Følner tilings for actions of amenable groups
• Tilings in graphons
• Suboptimality of local algorithms for a class of max-cut problems
• Lower matching conjecture, and a new proof of Schrijver's and Gurvits's theorems
• 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
• Perfect matchings as IID factors on non-amenable groups
• On Baire measurable colorings of group actions
• 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

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)