Search

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2009.03.016 Byline: Jurij MiheliA (a), Amine Mahjoub (b), Christophe Rapine (c), Borut RobiA (a) Keywords: Complexity theory; Uncertainty modeling; Scenarios; Combinatorial optimization; Decision analysis; Network flows Abstract: A significant input-data uncertainty is often present in practical situations. One approach to coping with this uncertainty is to describe the uncertainty with scenarios. A scenario represents a potential realization of the important parameters of the problem. In this paper we apply a recent approach, called flexibility, to solving two-stage flexible-choice problems. The first stage represents the present, where a decision maker must plan ahead to make a decision to hedge against uncertainty in the second stage, which represents the uncertain future, and is described as a set of scenarios. When one of the future scenarios is realized, a decision maker is willing to pay some recourse cost to augment the earlier solution to be more suitable for the realized scenario. Since all of the future scenarios are known, it is reasonable to presume that their desired solutions are also known. Thus, the aim of a decision maker is to find a solution in the present that is as easy as possible to adapt to solutions in the future. In this paper we study the problem where feasible solutions of the first stage are all p-element subsets of some finite set, and the solutions of the second stage are fixed p-element subsets. We present computational complexity results and algorithms for two versions of the two-stage flexible-choice problem. We formally define both problems, i.e., the sum-flexibility problem and the max-flexibility problem. For the sum-flexibility problem we describe an exact polynomial-time algorithm for the 3-scenario version, and we show non-approximability for the 4-scenario version. For the max-flexibility problem we show that the 3-scenario version is NP-hard, but approximable within a constant performance guarantee. Additionally, we prove non-approximability for the 4-scenario version of the problem. Author Affiliation: (a) Faculty of Computer and Information Science, University of Ljubljana, Ljubljana, Slovenia (b) UTIC, Higher School of Sciences and Techniques of Tunis, Tunis, Tunisia (c) G-SCOP Laboratory, Grenoble, France Article History: Received 11 March 2008; Accepted 12 March 2009

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.sysarc.2005.12.003 Byline: TomaA3/4 Dobravec (a), Janez A1/2erovnik (b)(c), Borut RobiA (a) Keywords: Circulant networks; Two-terminal routing; Restricted shortest paths; Algorithm design Abstract: A k-circulant network G(n; h.sub.1, h.sub.2,..., h.sub.k) is an undirected graph where the node set is Z.sub.n={0,1,...,n-1} and the edge set is the union of sets of unordered pairs E.sub.i={(u,u+sign(i)ah.sub.|i|(modn))|u[member of]Z.sub.n}, for i [member of]{-k,...,-1,1,..., k}. We present an optimal (i.e. using shortest paths) dynamic two-terminal message routing algorithm for k-circulant networks, k [greater than or equal to]2. Instead of computing the shortest paths in advance or using routing tables, our algorithm uses only the address of the final destination to determine the next node to which the message must be sent in order to stay on one of the shortest paths to its destination. We introduce the restricted shortest paths, which are used by our routing algorithm, and present an efficient algorithm for their construction in 2-circulant graphs. Author Affiliation: (a) Faculty of Computer and Information Science, University of Ljubljana, TrA3/4aA ka 25, Ljubljana, Slovenia (b) Faculty of Mechanical Engineering, University of Maribor, Smetanova 17, Maribor, Slovenia (c) Institute of Mathematics, Physics and Mechanics, Jadranska 19, Ljubljana, Slovenia Article History: Received 28 June 2004; Revised 1 September 2005; Accepted 23 December 2005