Approximating Some Network Design Problems With Node Costs

Download Now Date Added: Jun 2009
Format: PDF

Network design problems require finding a minimum cost (sub-)network that satisfies prescribed properties, often connectivity requirements. The most fundamental problems are the ones with 0, 1 connectivity requirements. Classic examples are: Shortest Path, Min-Cost Spanning Tree, Min-Cost Steiner Tree/Forest, Traveling Salesperson, and others. Examples of problems with high connectivity requirements are: Min-Cost k-Flow, Min-Cost k-Edge/Node-Connected Spanning Subgraph, Steiner Network, and others. All these problems also have practical importance in applications. Two main types of costs are considered in the literature: the edge costs and the node costs.