Borel oracles. An analytical approach to constant-time algorithms

In 2008 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 a...

Full description

Saved in:
Bibliographic Details
Published in:Proceedings of the American Mathematical Society 2010-08, Vol.138 (8), p.2939-2947
Main Authors: ELEK, GÁBOR, LIPPNER, GÁBOR
Format: Article
Language:English
Subjects:
Approximation algorithms
Combinatorics
Combinatorics. Ordered structures
Exact sciences and technology
General mathematics
General, history and biography
Graph theory
Mathematics
Neighborhoods
Oracles
Sciences and techniques of general use
Vertices
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In 2008 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.
ISSN:0002-9939
1088-6826
DOI:10.1090/S0002-9939-10-10291-3