Search

Abstract: The Steiner Forest Problem (SFP for short) is a natural generalization of the classical Steiner Tree Problem. Instead of only one terminal net there is given a set of terminal nets that have to be connected by choosing edges at minimum cost. Richey and Parker [M.B. Richey, R.G. Parker, On multiple Steiner subgraph problems, Networks 16 (4) (1986) 423–438] posed the question whether SFP is hard on series-parallel graphs. We partially answer this question by showing that SFP is strongly -hard on graphs with treewidth 3. On the other hand, a quadratic time algorithm for the special case on outerplanar graphs is suggested. Since series-parallel graphs have treewidth 2 and outerplanar graphs are series-parallel, we almost close the gap between polynomially solvable and hard cases. [Copyright &y& Elsevier]

Abstract: In this paper, we consider the Online Target Date Assignment Problem (OnlineTDAP) for general downstream problems, where the downstream cost are nonnegative, additive and satisfy the triangle inequality. We analyze algorithm smart, which was introduced by Angelelli et al. and give its exact competitive ratio depending on the number of requests. Since the obtained competitive ratio is at most we answer the question posed in Angelelli et al. if smart has a competitive ratio strictly less than . Moreover, we introduce a new algorithm called clever and show that this strategy has a competitive ratio of . We show that this is asymptotically optimal by proving that no online algorithm can perform better than . [Copyright &y& Elsevier]

Abstract: This paper concerns the reverse 2-median problem on trees and the reverse 1-median problem on graphs that contain exactly one cycle. It is shown that both models under investigation can be transformed to an equivalent reverse 2-median problem on a path. For this new problem an algorithm is proposed, where n is the number of vertices of the path. It is also shown that there exists an integral solution if the input data are integral. [Copyright &y& Elsevier]