-
作者：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...
-
作者：Cánovas, MJ; López, MA; Parra, J
作者单位：Universidad Miguel Hernandez de Elche; Universitat d'Alacant
摘要：In this paper, we consider a parametric family of convex inequality systems in the Euclidean space, with an arbitrary infinite index set, T, and convex constraints depending continuously on a parameter ranging in a separable metric space. No structure is assumed for T, and so the dependence of the constraints on the index has no particular property. In this context, the possibility of approaching the nominal system by means of sequences of finite subsystems associated to proximal parameters is...
-
作者：Guenin, B
作者单位：University of Waterloo
摘要：A family of sets H is ideal if the polyhedron {x greater than or equal to 0:Sigma(iis an element ofS) x(i).greater than or equal to 1, For All S is an element of H} is integral. Consider a graph G with vertices s, t. An odd st-walk is either an odd st-path or the union of an even st-path and an odd circuit that share, at most, one vertex. Let T be a subset of vertices of even cardinality. An st-T-cut is a cut of the form delta(U) where \U boolean AND T\ is odd and U contains exactly one of s o...
