Computational experiments with a lazy version of a <Emphasis Type="Italic">K</Emphasis> quickest simple path ranking algorithm

The quickest path problem is related to the classical shortest path problem, but its objective function concerns the transmission time of a given amount of data throughout a path, which involves both cost and capacity. The K-quickest simple paths problem generalises the latter, by looking for a given number K of simple paths in non-decreasing order of transmission time. Two categories of algorithms are known for ranking simple paths according to the transmission time. One is the adaptation of deviation algorithms for ranking shortest simple paths (Pascoal et al. in Comput. Oper. Res. 32(3):509–520, 2005; Rosen et al. in Comput. Oper. Res. 18(6):571–584, 1991), and another is based on ranking shortest simple paths in a sequence of networks with fixed capacity lower bounds (Chen in Inf. Process. Lett. 50:89–92, 1994), and afterwards selecting the K quickest ones. After reviewing the quickest path and the K-quickest simple paths problems we describe a recent algorithm for ranking quickest simple paths (Pascoal et al. in Ann. Oper. Res. 147(1):5–21, 2006). This is a lazy version of Chen’s algorithm, able to interchange the calculation of new simple paths and the output of each k-quickest simple path. Finally, the described algorithm is computationally compared to its former version, as well as to deviation algorithms.      

The multichoice coalition value

In this paper we define a solution for multichoice games which is a generalization of the Owen coalition value (Lecture Notes in Economics and Mathematical Systems: Essays in Honor of Oskar Morgenstern, Springer, New York, pp. 76–88, 1977) for transferable utility cooperative games and the Egalitarian solution (Peters and Zanks, Ann. Oper. Res. 137, 399–409, 2005) for multichoice games. We also prove that this solution can be seen as a generalization of the configuration value and the dual configuration value (Albizuri et al., Games Econ. Behav. 57, 1–17, 2006) for transferable utility cooperative games.     

Improved algorithms for the multicut and multiflow problems in rooted trees

Costa et al. (Oper. Res. Lett. 31:21–27, 2003) presented a quadratic O(min (Kn,n ²)) greedy algorithm to solve the integer multicut and multiflow problems in a rooted tree. (n is the number of nodes of the tree, and K is the number of commodities). Their algorithm is a special case of the greedy type algorithm of Kolen (Location problems on trees and in the rectilinear plane. Ph.D. dissertation, 1982) to solve weighted covering and packing problems defined by general totally balanced (greedy) matrices. In this communication we improve the complexity bound in Costa et al. (Oper. Res. Lett. 31:21–27, 2003) and show that in the case of the integer multicut and multiflow problems in a rooted tree the greedy algorithm of Kolen can be implemented in subquadratic O(K+n+min (K,n)log n) time. The improvement is obtained by identifying additional properties of this model which lead to a subquadratic transformation to greedy form and using more sophisticated data structures.      

A note on coalitional manipulation and centralized inventory management

In this note we deal with inventory games as defined in Meca et al. (Math. Methods Oper. Res. 57:483–491, 2003). In that context we introduce the property of immunity to coalitional manipulation, and demonstrate that the SOC-rule (Share the Ordering Cost) is the unique allocation rule for inventory games which satisfies this property. The authors acknowledge the financial support of Ministerio de Educación y Ciencia, FEDER and Xunta de Galicia through projects SEJ2005-07637-C02-02 and PGIDIT06PXIC207038PN.     

RETRACTED ARTICLE: Convergence of Weighted Sums for Arrays of Negatively Dependent Random Variables and Its Applications

We discuss the complete convergence of weighted sums for arrays of rowwise negatively dependent random variables (ND r.v.’s) to linear processes. As an application, we obtain the complete convergence of linear processes based on ND r.v.’s which extends the result of Li et al. (Stat. Probab. Lett. 14:111–114, 1992), including the results of Baum and Katz (Trans. Am. Math. Soc. 120:108–123, 1965), from the i.i.d. case to a negatively dependent (ND) setting. We complement the results of Ahmed et al. (Stat. Probab. Lett. 58:185–194, 2002) and confirm their conjecture on linear processes in the ND case.     

A note on Ceng-Wang-Yao’s result [Strong convergence theorems by a relaxed extragradient method for a general system of variational inequalities,Math. Meth. Oper. Res. (2008) 67: 375–390]

In this paper, we give a short and simple proof of the recent result of Ceng et al. (Math Methods Oper Res 67(3):375–390, 2008).     

Convexity properties for interior operator games

Interior operator games arose by abstracting some properties of several types of cooperative games (for instance: peer group games, big boss games, clan games and information market games). This reason allow us to focus on different problems in the same way. We introduced these games in Bilbao et al. (Ann. Oper. Res. 137:141–160, 2005) by a set system with structure of antimatroid, that determines the feasible coalitions, and a non-negative vector, that represents a payoff distribution over the players. These games, in general, are not convex games. The main goal of this paper is to study under which conditions an interior operator game verifies other convexity properties: 1-convexity, k-convexity (k≥2 ) or semiconvexity. But, we will study these properties over structures more general than antimatroids: the interior operator structures. In every case, several characterizations in terms of the gap function and the initial vector are obtained. We also find the family of interior operator structures (particularly antimatroids) where every interior operator game satisfies one of these properties.     

Dynamic Walrasian price equilibrium problem: evolutionary variational approach with sensitivity analysis

Many authors have been devoted to the study of the static general economic equilibrium problem regulated to Walras’ law (see e.g. Arrow and Debreu in Econometrica 22:265–290, 1954; Arrow and Hahn in General competitive analysis, 1991; Arrow et al. in Econometrica 27:82–109, 1959; Border in Fixed point theorems with application to economics and game theory, Cambridge University Press, Cambridge, 1985; Dafermos in Math Programm 46:391–402, 1990; Dafermos and Zhao in Oper Res Lett 10:396–376, 1991; Donato et al. in J Glob Optim, 2007; Hahn in Stability, North Holland, Amsterdam, 1982; Jofré et al. in Math Oper Res, 2007; Nagurney in Network economics—a variational inequality approach, Kluwer, Dordrecht, 1999; Nagurney and Zhao in Network formalism for pure exchange economic equilibria, World Scientific Press, Singapore, 1993; Walker in J Polit Econ 94(4), 1987; Walras in Elements d’Economique Politique Pure, Corbaz, Lausanne, Switzerland, 1874; Zhao in Variational inequalities in general equilibrium: analysis and computation, PhD thesis, Brown University, 1988; and their bibliography). The aim of this paper is to provide a first approach to a particular dynamic general economic equilibrium problem: a Walrasian price equilibrium problem when the data are time-dependent. The equilibrium conditions that describe this pure exchange economic model are expressed in terms of an evolutionary variational inequality, for which existence and sensitivity results are given. Moreover, our problem can be expressed in a common way to many other equilibrium problems.     

<Emphasis Type="Italic">p</Emphasis>-additive games: a class of totally balanced games arising from inventory situations with temporary discounts

We introduce a new class of totally balanced cooperative TU games, namely p-additive games. It is inspired by the class of inventory games that arises from inventory situations with temporary discounts (Toledo Ph.D. thesis, Universidad Miguel Hernández de Elche, 2002) and contains the class of inventory cost games (Meca et al. Math. Methods Oper. Res. 57:481–493, 2003). It is shown that every p-additive game and its corresponding subgames have a nonempty core. We also focus on studying the character of concave or convex and monotone p-additive games. In addition, the modified SOC-rule is proposed as a solution for p-additive games. This solution is suitable for p-additive games, since it is a core-allocation which can be reached through a population monotonic allocation scheme. Moreover, two characterizations of the modified SOC-rule are provided. This work was partially supported by the Spanish Ministry of Education and Science and Generalitat Valenciana (grants MTM2005-09184-C02-02, ACOMP06/040, CSD2006-00032). Authors acknowledge valuable comments made by the Editor and the referee.     

On Implicit Multifunction Theorems

We give implicit multifunction results generalizing to multifunctions the Robinson’s implicit function theorem (Robinson, Math Oper Res 16(2):292–309, 1991). To this end, we use parametric error bounds estimates for a suitable function refining the one given in Azé and Corvellec (ESAIM Control Optim Calc Var 10:409–425, 2004). Sharp approximations of the implicit multifunctions are given extending the results of Nachi and Penot (Control Cybernet 35:871–901, 2005). Dedicated to Boris Mordukhovich in honour of his 60th birthday.     

Strong Limit Theorems for Weighted Sums of Negatively Associated Random Variables

In this paper, we establish strong laws for weighted sums of identically distributed negatively associated random variables. Marcinkiewicz-Zygmund’s strong law of large numbers is extended to weighted sums of negatively associated random variables. Furthermore, we investigate various limit properties of Cesàro’s and Riesz’s sums of negatively associated random variables. Some of the results in the i.i.d. setting, such as those in Jajte (Ann. Probab. 31(1), 409–412, 2003), Bai and Cheng (Stat. Probab. Lett. 46, 105–112, 2000), Li et al. (J. Theor. Probab. 8, 49–76, 1995) and Gut (Probab. Theory Relat. Fields 97, 169–178, 1993) are also improved and extended to the negatively associated setting.      

Sequencing games without initial order

In this note we study uncertainty sequencing situations, i.e., one-machine sequencing situations in which no initial order is specified. We associate cooperative games with these sequencing situations, study their core, and provide links with the classic sequencing games introduced by Curiel et al. (Eur J Oper Res 40:344–351, 1989). Moreover, we propose and characterize two simple cost allocation rules for uncertainty sequencing situations with equal processing times.     

Comments on “Scheduling jobs on a k-stage flexible flow-shop” [Annals of Operations Research (2008) 164: 29–40]

The problem of makespan minimization on a flexible flow shop with k stages and m _s machines at any stage proposed by Paternina-Arboleda et al. [Ann. Oper. Res. 164:29–40, 2008] was recently published in Annals of Operations Research journal to solve the flexible flow-shop scheduling problems. In this work, some comments and suggestions are given to the paper. The comment is about the proposed mathematical formulation and the modification of it is suggested.     

Returns to scale in multiplicative models in data envelopment analysis

One class of models introduced in DEA is called multiplicative models, in which, as shown by Banker and Maindiratta (Manag. Sci. 32:126–135, 1986), the piecewise linear frontiers usually employed in DEA are replaced by a frontier that is piecewise Cobb-Douglas(=log  linear). Banker and Maindiratta (Manag. Sci. 32:126–135, 1986) introduced a model to identify the most productive scale size pattern, and Banker et al. (Eur. J. Oper. Res. 154:345–362, 2004) presented a two-stage method for the identification of returns to scale (RTS) in multiplicative models. In this paper it is shown that both the RTS situation and the MPSS pattern could be determined by a single model in one step. The new method is important in the computational point of view.     

No end of the world in 2012 for 4OR

The purpose of this note is to give the readers of 4OR information on the state of the journal and its future, abiding by a triennial tradition which started with Bouyssou et al. (4OR 1(1):1–6, 2003) and continued with Bouyssou et al. (4OR 4(1):1–9, 2006) and Bouyssou et al. (4OR Q J Oper Res 7(1):15, 2009). In the 3 years that have passed since the last editorial note, three volumes of the journal have been published, each containing four issues: vol. 7 (2009), vol. 8 (2010) and vol. 9 (2011).     

On Topological Properties of Min-Max Functions

We examine the topological structure of the upper-level set M ^max given by a min-max function φ. It is motivated by recent progress in Generalized Semi-Infinite Programming (GSIP). Generically, M ^max is proven to be the topological closure of the GSIP feasible set (see Guerra-Vázquez et al. 2009; Günzel et al., Cent Eur J Oper Res 15(3):271–280, 2007). We formulate two assumptions (Compactness Condition CC and Sym-MFCQ) which imply that M ^max is a Lipschitz manifold (with boundary). The Compactness Condition is shown to be stable under C ⁰-perturbations of the defining functions of φ. Sym-MFCQ can be seen as a constraint qualification in terms of Clarke’s subdifferential of the min-max function φ. Moreover, Sym-MFCQ is proven to be generic and stable under C ¹-perturbations of the defining functions which fulfill the Compactness Condition. Finally we apply our results to GSIP and conclude that generically the closure of the GSIP feasible set is a Lipschitz manifold (with boundary).     

Proposal of a new distribution in PERT methodology

The aim of this paper is to present the generalized biparabolic distribution (GBP) as a good candidate to be utilized as the distribution underlying to PERT methodology (Malcolm et al. in Oper. Res. 7:646–669, 1959). To do this and following the criteria established by Taha (Investigación de Operaciones, 1981) and Herrerías (Estudios de Economía Aplicada, pp. 89–112, 1989), we will compare the mean and variance estimates derived from each proposed density function, viz beta, two-sided power (TSP) and GBP distributions. Also we will compare the estimates contributed by the mesokurtic and of constant variance families of the aforementioned distributions. The main conclusion is that the GBP distribution is the most convenient to be used in the PERT methodology because its mean is almost as moderate as that of trapezoidal and its variance is much higher than that of the rest of distributions. As a consequence, it can be stated that the GBP distribution is an alternative to the other four-parameter distributions.     

The <Emphasis Type="Italic">M</Emphasis>/<Emphasis Type="Italic">M</Emphasis>/1 retrial queue with retrials due to server failures

Sherman and Kharoufeh (Oper. Res. Lett. 34:697–705, [2006]) considered an M/M/1 type queueing system with unreliable server and retrials. In this model it is assumed that if the server fails during service of a customer, the customer leaves the server, joins a retrial group and in random intervals repeats attempts to get service. We suggest an alternative method for analysis of the Markov process, which describes the functioning of the system, and find the joint distribution of the server state, the number of customers in the queue and the number of customers in the retrial group in steady state.      

The multi-core,balancedness and axiomatizations for multi-choice games

This note extends the solution concept of the core for cooperative games to multi-choice games. We propose an extension of the theorem of Bondareva (Problemy Kybernetiki 10:119–139, 1963) and Shapley (Nav Res Logist Q 14:453–460, 1967) to multi-choice games. Also, we introduce a notion of reduced games for multi-choice games and provide an axiomatization of the core on multi-choice games by means of corresponding notion of consistency and its converse.     

A note on the proof of the complexity of the little-preemptive open-shop problem

We give a complement note on the proof of the NP-hardness of preemptive acyclic open-shop problem presented earlier by the authors in Ann. Oper. Res. 159:183–213, 2008.