Invited Session Thu.1.H 3008

Thursday, 10:30 - 12:00 h, Room: H 3008

Cluster 2: Combinatorial optimization [...]

Resource placement in networks


Chair: David S. Johnson



Thursday, 10:30 - 10:55 h, Room: H 3008, Talk 1

David S. Johnson
Disjoint path facility location: Theory and practice

Coauthors: Lee Breslau, Ilias Diakonikolas, Nick Duffield, Yu Gu, Mohammadtaghi Hajiaghayi, Howard Karloff, Mauricio Resende, Subharata Sen


We consider the following problem: Given a directed graph G=(V,A) with weights on the arcs, together with subsets C (customers) and F (potential facility locations) of V, find a subset F' of F such that, for every c in C, either c is in F' or there exist two vertices f, f' in F' such that no shortest path from c to f shares any vertex other than c with any shortest path from c to f' (a restriction required when routing is done by the OSPF protocol with path-splitting). This "cover by pairs'' problem has potential applications to network monitoring and to the distribution of time-critical streaming content. Theoretical results suggest that no algorithm can be guaranteed to get within even a polylogarithmic factor of optimal for our problem, and MIP-based optimization approaches become infeasible for graphs with more than about 100 vertices. However a collection of heuristics we devised succeeded in finding optimal solutions to all the instances in our testbed of synthetic and real-world instances, with sizes ranging up to 1000 vertices, as verified by computing a (much easier) MIP-based lower bound. We describe the applications, theory, algorithms, bounds, and experimental results.



Thursday, 11:00 - 11:25 h, Room: H 3008, Talk 2

David Applegate
Using an exponential potential function method to optimize video-on-demand content placement

Coauthors: Aaron Archer, Vijay Gopalakrishnan, Seungjoon Lee, K.k. Ramakrishnan


For a large-scale Video-on-Demand service, as the library size grows, it becomes important to balance the disk space necessary to store content locally at the requesting node with the bandwidth required to serve requests from remote nodes. This gives rise to the problem of deciding which content to place at which serving nodes, taking into account the resource constraints (disk and bandwidth) and content attributes (request patterns, size, and bandwidth).
We model this optimization problem as a mixed-integer program. However, even for moderately large instances (20,000 videos, 50 serving nodes), the linear relaxation becomes intractable for off-the-shelf linear programming solvers, both in terms of time and memory use. Instead, we approximately solve the linear relaxation by using a Lagrangian decomposition approach based on exponential potential functions, and then round that solution to an integer solution.
Computational experiments on a testbed of synthetic and real-world instances show that this decomposition approach typically reduces the running time by orders of magnitude, while achieving solutions within 2% of optimal with no constraint violated by more than 1%.


  There are three major facts that should be watched out for in all payday loans in the United States. What can cause long-term use of Canadian Viagra? In the network and other sources of information, there is no reliable data on the long-term use of Viagra and its negative effects on the body.