Random restricted matching and lower bounds for combinatorial optimization

Random restricted matching and lower bounds for combinatorial optimization

0.00 Avg rating—0 Votes
Article ID: iaor20125705
Volume: 24
Issue: 3
Start Page Number: 280
End Page Number: 298
Publication Date: Oct 2012
Journal: Journal of Combinatorial Optimization
Authors:
Keywords: graphs
Abstract:

We prove results on optimal random extensions of trees over points in [0,1] d . As an application, we give a general framework for translating results from combinatorial optimization about the behaviour of random points into results for point sets with sufficiently high regularity. We furthermore introduce a new irregularity problem concerning Voronoi cells, which has applications in logistics.

Reviews

Required fields are marked *. Your email address will not be published.