-
作者：Monteiro, RDC; Zanjácomo, PR
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：Extending the previous work of Monteiro and Pang (1998), this paper studies properties of fundamental maps that can be used to describe the central path of the monotone nonlinear complementarity problems over the cone of symmetric positive semidefinite matrices. Instead of focusing our attention on a specific map as was done in the approach of Monteiro and Pang (1998), this paper considers a general form of a fundamental map and introduces conditions on the map that allow us to extend the main...
-
作者：Xu, SH; Li, HJ
作者单位：Pennsylvania Commonwealth System of Higher Education (PCSHE); Pennsylvania State University; Pennsylvania State University - University Park; Washington State University
摘要：Stochastic models with simultaneous arrivals arise naturally in the areas such as synchronized communication networks, flexible manufacturing systems, production/inventory systems, reliability modeling in random environment, etc., with a wide variety of interpretations. Simultaneous arrivals introduce dependence among various components of the system and make the explicit solutions of joint system performance measures either computationally intensive or intractable. This calls for structural a...
-
作者：Kannai, Y; Wooders, MH
作者单位：Weizmann Institute of Science; University of Toronto
摘要：Reny and Wooders (1998) showed that there is some point in the intersection of sets in Shapley's (1973) generalization of the Knaster-Kuratowski-Mazurkiwicz Theorem with the property that the collection of all sets containing that point is partnered as well as balanced. We provide a further extension by showing that the collection of all such sets can be chosen to be strictly balanced, implying the Reny-Wooders result. Our proof is topological, based on the Eilenberg-Montgomery Fixed Point The...
-
作者：Skutella, M; Woeginger, GJ
作者单位：Technical University of Berlin; Graz University of Technology
摘要：We consider the problem of scheduling a set of n jobs on m identical parallel machines so as to minimize the weighted sum of job completion limes. This problem is NP-hard in the strong sense. The best approximation result known so far was a 1/2 (1 + root 2)-approximation algorithm that has been derived by Kawaguchi and Kyan back in 1986. The contribution of this paper is a polynomial time approximation scheme for this setting, which settles a problem that was open for a long time. Moreover, ou...
-
作者：Rosenberg, D; Vieille, N
作者单位：Universite Paris 13; Universite de Bordeaux; Institut Polytechnique de Paris; Ecole Polytechnique
-
作者：Chen, H; Zhang, HQ
作者单位：University of British Columbia; Chinese Academy of Sciences
摘要：The diffusion approximation is proved for a class of multiclass queueing networks under FIFO service disciplines. Ln addition to the usual assumptions for a heavy traffic limit theorem, a key condition that characterizes this class is that a J x J matrix G, known as the workload contents matrix, has a spectral radius less than unity, where J represents the number of sen ice stations. The (j, l)th component of matrix G can be interpreted as the long-run average amount of future work for station...
-
作者：Shigeno, M; Iwata, S; McCormick, ST
作者单位：University of Tsukuba; University of Osaka; University of British Columbia
摘要：This paper presents two new scaling algorithms for the minimum cost network flow problem, one a primal cycle canceling algorithm, the other a dual cut canceling algorithm. Both algorithms scale a relaxed optimality parameter, and create a second, inner relaxation. The primal algorithm uses the inner relaxation to cancel a most negative node-disjoint Family of cycles w.r.t. the scaled parameter, the dual algorithm uses it to cancel most positive cuts w.r.t. the scaled parameter. We show that in...
-
作者：Aardal, K; Hurkens, CAJ; Lenstra, AK
作者单位：Utrecht University; Eindhoven University of Technology
摘要：We develop an algorithm for solving a system of diophantine equations with lower and upper bounds on the variables. The algorithm is based on lattice basis reduction. It first rinds a short vector satisfying the system of diophantine equations, and a set of Vectors belonging to the null-space of the constraint matrix. Due to basis reduction, all these vectors are relatively short. The next step is to branch on linear combinations of the null-space vectors, which either yields a vector that sat...
-
作者：Bonnans, JF; Haddou, M
作者单位：Inria; Universite de Orleans
摘要：This paper is devoted to the mathematical study of a routing problem in telecommunication networks, when the cost function is the average delay of communications. We establish asymptotic expansions for the Value function and solutions in the vicinity of a congested nominal problem. The study is strongly related to the one of a partial inverse barrier method for linear programming.
-
作者：Molchanov, I; Zuyev, S
作者单位：University of Glasgow; University of Strathclyde
摘要：Let F(II) be a functional of a (generally nonhomogeneous) Poisson process II with intensity measure mu. Considering the expectation EmuF(II) as a functional of mu from the cone M of positive finite measures, we derive closed form expressions for its Frechet derivatives of an orders that generalize the perturbation analysis formulae for Poisson processes. Variational methods developed for the space mm allow us to obtain first and second order sufficient conditions for various types of constrain...
