-
作者：Grabisch, M; Marichal, JL; Roubens, M
作者单位：Sorbonne Universite; University of Liege; University of Liege
摘要：This paper introduces four alternative representations of a set function: the Mobius transformation, the co-Mobius transformation, and the interactions between elements of any subset of a given set as extensions of Shapley and Banzhaf values. The links between the five equivalent representations of a set function are emphasized in this presentation.
-
作者：Sun, XL; Li, D
作者单位：Shanghai University; Chinese University of Hong Kong
摘要：A logarithmic-exponential dual formulation is proposed in this paper for bounded integer programming problems. This new dual formulation possesses an asymptotic strong duality property and guarantees the identification of an optimal solution of the primal problem. These prominent features are achieved by exploring a novel nonlinear Lagrangian function, deriving an asymptotic zero duality gap, investigating the unimodality of the associated dual function and ensuring the primal feasibility of o...
-
作者：Anstreicher, KM
作者单位：University of Iowa
摘要：We consider the volumetric barrier for semidefinite programming, or generalized volumetric barrier, as introduced by Nesterov and Nemirovskii. We extend several fundamental properties of the Volumetric barrier for a polyhedral set to the semidefinite case. Our analysis facilitates a simplified proof of self-concordance for the semidefinite volumetric barrier, as well as for the combined volumetric-logarithmic barrier for semidefinite programming. For both of these barriers we obtain self-conco...
-
作者：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...
