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 Brinkman, Bo en_US Helmick, Michael en_US 2008-07-22T19:31:29Z en_US 2013-07-10T15:06:26Z 2008-07-22T19:31:29Z en_US 2013-07-10T15:06:26Z 2008-03-25 en_US 2008-04-17 en_US
dc.identifier.uri 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


My Account