Hitting Buneman Circles

Michael Fourman

Research output: Chapter in Book/Report/Conference proceedingChapter

Abstract

We discuss Peter Buneman’s suggestion that a fibre connection to the internet — a hub — should be available within every circle enclosing a population of at least 2,000 people (a b-circle). This poses the problem of finding a small set, H, of hubs, such that every b-circle contains a hub. We show that a greedy algorithm does not lead to an optimal set of hubs. Instead it models market forces, which are naturally greedy. An unfettered market will exploit the most profitable communities and, just like a greedy algorithm, leave gaps that it is uneconomic to fill. We describe a geometric heuristic for the discovery of efficient hub placements satisfying a purely combinatorial analogue of Buneman’s criterion, and apply it to illustrate the inherent inefficiency of gap-funding in a market-led broadband policy.
Original languageEnglish
Title of host publicationIn Search of Elegance in the Theory and Practice of Computation
Subtitle of host publicationEssays Dedicated to Peter Buneman
PublisherSpringer-Verlag GmbH
Pages250-258
Number of pages8
ISBN (Electronic)978-3-642-41660-6
ISBN (Print)978-3-642-41659-0
DOIs
Publication statusPublished - 2013

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin / Heidelberg
Volume8000
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Fingerprint

Dive into the research topics of 'Hitting Buneman Circles'. Together they form a unique fingerprint.

Cite this