Hyperfinite graphings and combinatorial optimization
L. Lovász. (2017)cite arxiv:1709.03179Comment: 25 pages, new version.
Abstract
We exhibit an analogy between the problem of pushing forward measurable sets
under measure preserving maps and linear relaxations in
combinatorialoptimization. We show how invariance of hyperfiniteness of
graphings under local isomorphism can be reformulated as an infinite version of
a natural combinatorial optimization problem, and how one can prove it by
extending well-known proof techniques (linear relaxation, greedy algorithm,
linear programming duality) from the finite case to the infinite.
Description
Hyperfinite graphings and combinatorial optimization
%0 Generic
%1 lovasz2017hyperfinite
%A Lovász, László
%D 2017
%K Lovasz combinatorial_optimization graphings
%T Hyperfinite graphings and combinatorial optimization
%U http://arxiv.org/abs/1709.03179
%X We exhibit an analogy between the problem of pushing forward measurable sets
under measure preserving maps and linear relaxations in
combinatorialoptimization. We show how invariance of hyperfiniteness of
graphings under local isomorphism can be reformulated as an infinite version of
a natural combinatorial optimization problem, and how one can prove it by
extending well-known proof techniques (linear relaxation, greedy algorithm,
linear programming duality) from the finite case to the infinite.
@misc{lovasz2017hyperfinite,
abstract = {We exhibit an analogy between the problem of pushing forward measurable sets
under measure preserving maps and linear relaxations in
combinatorialoptimization. We show how invariance of hyperfiniteness of
graphings under local isomorphism can be reformulated as an infinite version of
a natural combinatorial optimization problem, and how one can prove it by
extending well-known proof techniques (linear relaxation, greedy algorithm,
linear programming duality) from the finite case to the infinite.},
added-at = {2020-01-22T19:36:10.000+0100},
author = {Lovász, László},
biburl = {https://www.bibsonomy.org/bibtex/21f8d3a90eb632022ca38c3542eef9b5b/j.c.m.janssen},
description = {Hyperfinite graphings and combinatorial optimization},
interhash = {51082bd18fbb2e1f809c332de66a341e},
intrahash = {1f8d3a90eb632022ca38c3542eef9b5b},
keywords = {Lovasz combinatorial_optimization graphings},
note = {cite arxiv:1709.03179Comment: 25 pages, new version},
timestamp = {2020-01-22T19:36:10.000+0100},
title = {Hyperfinite graphings and combinatorial optimization},
url = {http://arxiv.org/abs/1709.03179},
year = 2017
}