The Prize-Collecting Steiner Tree Problem by Ivana Ljubic University of Vienna
 Intro: Let G = (V,E, c, p) be an undirected graph, with the vertices V associated with non-negative profits p, and with the edges E associated with non-negative costs c. The graph may correspond to the local street map, for example, with the edges representing street segments and vertices representing street intersections and the location of potential customers. The profit p associated with a vertex is an estimate of the potential gain of revenue caused by that customer being connected to the network and receiving its service. Vertices corresponding to street intersections have profit zero. The cost c associated with an edge is the cost of establishing the connection, i.e., of laying the pipe or cable on the corresponding street segment. Definition: The Linear Prize-Collecting Steiner Tree problem (PCST) consists of finding a connected subgraph T = (V' ,E' ) of G, that maximizes profit(T) which is defined as the sum of all node-prizes taken into the solution minus the costs of the edges needed to establish the network. Alternatively, one can minimize the edge-costs for establishing the network plus the penalties of the vertices outside of the solution.
 Input graph: hollow circles are customers A feasible but not optimal PCST solution