-
作者：Zalinescu, C
作者单位：Martin Luther University Halle Wittenberg
摘要：In a recent paper Li and Singer (1998) introduced the notion of global error bound for a convex multifunction at a point of its domain. They showed the existence of such a global error bound when the-image of the multifunction at the respective point is bounded and conjectured a result for the case when the image is not bounded. In this paper we solve their conjecture with a positive answer. For this we establish a criterion for the existence of a global error bound using the Pompeiu-Hausdorff...
-
作者：Lasserre, JB; Zeron, ES
作者单位：Centre National de la Recherche Scientifique (CNRS); Instituto Politecnico Nacional - Mexico
摘要：Given a convex rational polytope Omega(b) := {x is an element of R-+(n)\ Ax=b}, we consider the function b-->f (b), which counts the nonnegative integral points of Omega(b). A closed form expression of its Z-transform z-->F(z) is easily obtained so that f (b) can be computed as the inverse Z-transform of F. We then provide two variants of an inversion algorithm. As a by-product, one of the algorithms provides the Ehrhart polynomial of a convex integer polytope Omega. We also provide an alterna...
-
作者：Izmailov, AF; Solodov, MV
作者单位：Russian Academy of Sciences
摘要：We study local structure of a nonlinear mapping near points where standard regularity and/or smoothness assumptions need not be satisfied. We introduce a new concept of 2-regularity (a certain kind of second-order regularity) for a once differentiable mapping whose derivative is Lipschitz continuous. Under this 2-regularity condition, we obtain the representation theorem and the covering theorem (i.e., stability with respect to right-hand side perturbations) under assumptions that are weaker t...
-
作者：Villeneuve, S; Zanette, A
作者单位：Universite Paris Saclay; University of Udine
摘要：we propose two numerical methods for pricing American options on two stocks based on the ADI algorithm of Peaceman and Rachford (1955). We prove the stability and convergence of these schemes and establish a comparative result.
-
作者：Rubinov, AM; Huang, XX; Yang, XQ
作者单位：Hong Kong Polytechnic University
摘要：We examine the validity of the zero duality gap properties for two important dual schemes: a generalized augmented Lagrangian dual scheme and a nonlinear Lagrange-type dual scheme. The necessary and sufficient conditions for the zero duality gap property to hold are established in terms of the lower semicontinuity of the perturbation functions.
-
作者：Wayne, KD
作者单位：Princeton University
摘要：We propose the first combinatorial solution to the generalized minimum cost flow problem (flow with losses and gains). Despite a rich history dating back to Kantorovich and Dantzig, until now, the only known way to solve the problem in polynomial-time was via general-purpose linear programming techniques. Polynomial combinatorial algorithms were previously known only for the version of our problem without costs. We design the first such algorithms for the version with costs. Our algorithms als...
-
作者：Cai, MC; Deng, XT; Zang, WN
作者单位：Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS; City University of Hong Kong; University of Hong Kong
摘要：We establish a necessary and sufficient condition for the linear system {x : Hx greater than or equal to e, x greater than or equal to 0} associated with a bipartite tournament to be totally dual integral, where H is the cycle-vertex incidence matrix and e is the all-one vector. The consequence is a min-max relation on packing and covering cycles, together with strongly polynomial time algorithms for the feedback vertex set problem and the cycle packing problem on the corresponding bipartite t...
-
作者：Frank, A; Shepherd, B; Tandon, V; Végh, Z
作者单位：Eotvos Lorand University; AT&T; Alcatel-Lucent; Lucent Technologies
摘要：We consider the node-capacitated routing problem in an undirected ring network along with its fractional relaxation, the node-capacitated multicommodity flow problem. For the feasibility problem, Farkas' lemma provides a characterization for general undirected graphs, asserting roughly that there exists such a flow if and only if the so-called distance inequality holds for every choice of distance functions arising from nonnegative node weights. For rings, this (straightforward) result will be...
-
作者：Gamarnik, D
作者单位：International Business Machines (IBM); IBM USA
摘要：We investigate stability of scheduling policies in queueing systems. To this day no algorithmic characterization exists for checking stability of a given policy in a given queueing system, In this paper we introduce a certain generalized priority, policy and prove that the stability of this policy is algorithmically undecidable. We also prove that stability of a homogeneous random walk in F-+(d) is undecidable. Finally, we show that the problem of computing a fluid limit of a queueing system o...
-
作者：Bar-Noy, A; Bhatia, R; Naor, JS; Schieber, B
作者单位：City University of New York (CUNY) System; Brooklyn College (CUNY); AT&T; Alcatel-Lucent; Lucent Technologies; Technion Israel Institute of Technology; International Business Machines (IBM); IBM USA
摘要：We study the problem of scheduling activities of several types under the constraint that, at most, a fixed number of activities can be scheduled in any single time slot An given activity type is associated with a service cost and an operating cost that increases linearly with the number of time slots since the last service of this typed The problem is to find an optimal schedule that minimizes the long-run average cost per time slot. Applications of such a model are the scheduling of maintenan...
