Scholarly Commons

An electronic repository for the intellectual products of the Miami University community

Degree-constrained Minimum Latency Trees are APX-Hard

DSpace/Manakin Repository

Show simple item record

dc.contributor.author Brinkman, Bo en_US
dc.contributor.author Helmick, Michael en_US
dc.date.accessioned 2008-07-22T19:31:29Z en_US
dc.date.accessioned 2013-07-10T15:06:26Z
dc.date.available 2008-07-22T19:31:29Z en_US
dc.date.available 2013-07-10T15:06:26Z
dc.date.issued 2008-03-25 en_US
dc.date.submitted 2008-04-17 en_US
dc.identifier.uri
dc.identifier.uri http://hdl.handle.net/2374.MIA/227 en_US
dc.description.abstract When transmitting data from a single source to many recipients, it is often desirable to use some recipients of the stream to re-broadcast the stream to other users. In such multicast systems each client may be used as a server, serving up to B other clients. Formally, we will take a set X of clients, along with a distance function d that specifies the latency (in the host network) between each pair of clients in X. Our goal will be to produce a directed spanning tree of X, rooted at some specified root 2 X, with out-degree bounded by B, and minimizing the sum of the latencies from root to every point in X. In addition to being motivated by current experimental algorithms work, the problem also interpolates naturally between the traveling repairman problem (when B = 1) and single source shortest paths (when B = n − 1). The former problem is APX-complete (in metric spaces) and the latter is in P. We explore the hardness of the problem for other values of B. In particular, we show that the problem remains APX-Hard at least up to B = Cpn for some universal constant C when the host space is a general semi-metric. en_US
dc.title Degree-constrained Minimum Latency Trees are APX-Hard en_US
dc.type Text en_US
dc.type.genre Article en_US


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search SC


Advanced Search

Browse

My Account