-
作者：GOLDSCHMIDT, O; HOCHBAUM, DS
作者单位：University of California System; University of California Berkeley; University of California System; University of California Berkeley
摘要：The k-cut problem is to find a partition of an edge weighted graph into k nonempty components, such that the total edge weight between components is minimum. This problem is NP-complete for an arbitrary k and its version involving fixing a vertex in each component is NP-hard even for k = 3. We present a polynomial algorithm for k fixed, that runs in O(n(k2/2-3k/2+4)T(n, m)) steps, where T(n, m) is the running time required to find the minimum (s, t)-cut on a graph with n vertices and m edges.
-
作者：PUHALSKII, A
作者单位：Russian Academy of Sciences
摘要：New results are obtained on the connection between the invariance principle for the first passage time process and that for the underlying processes. The main contribution is that the 'passing' process may have general drift. An example of the application is given which shows that this is of use in deriving limit theorems for delays from limit theorems for queue lengths when studying queueing systems with queue-dependent arrival or (and) service completion rates.
-
作者：SHAPIRO, A
摘要：We study continuity properties of optimal solutions of parametrized semi-infinite programming problems. The involved constraints are formulated in a form of cone constraints and then a slightly modified general result of Shapiro and Bonnans (1992) on Lipschitzian stability of optimal solutions is applied. It is shown that under certain second-order sufficient conditions, optimal solutions of the semi-infinite programs are Lipschitzian stable provided a regularity assumption related to a linear...
-
作者：LUC, DT; THERA, M
作者单位：Universite de Limoges
摘要：A new concept of derivative is introduced reflecting the global, rather than the local, behavior of a given function. Basic properties and calculus rules for this derivative are provided. Then they are applied to establish some characterizations of convex functions and some optimality conditions in mathematical programming.
-
作者：RALPH, D
摘要：A natural damping of Newton's method for nonsmooth equations is presented. This damping, via the path search instead of the traditional line search, enlarges the domain of convergence of Newton's method and therefore is said to be globally convergent. Convergence behavior is like that of line search damped Newton's method for smooth equations, including Q-quadratic convergence rates under appropriate conditions. Applications of the path search include damping Robinson-Newton's method for nonsm...
-
作者：HUANG, Y; KALLENBERG, LCM
摘要：This paper proves constructively the existence of optimal policies for maximum one-period mean-to-standard-deviation-ratio, negative variance-with-bounded-mean and mean-penalized-by-variance Markov decision chains by reducing them to a related mathematical program. This program entails maximizing (xB/D(xb)) + C(xb) over x in a polytope and with given bounds on xb where C and D are convex and either D is constant or D is positive and nondecreasing, C is nondecreasing and xB is nonpositive. This...
-
作者：KOVALYOV, MY; POTTS, CN; VANWASSENHOVE, LN
作者单位：INSEAD Business School; University of Southampton
摘要：This paper studies approximation algorithms for the problem of nonpreemptively scheduling n jobs on a single machine to minimize total weighted late work, where the late work for a job is the amount of processing of this job that is performed after its due date. A family of approximation algorithms {DP(epsilon)} is derived. For any epsilon > 0, DP(epsilon) delivers a schedule having total weighted late work which does not exceed (1 + epsilon) times that of an optimal schedule. Since DP(epsilon...
-
作者：KRICHAGINA, EV; LOU, SXC; TAKSAR, MI
作者单位：State University of New York (SUNY) System; Stony Brook University
摘要：We consider the control of a manufacturing system producing one product. The demand for this product is random. The manager can produce the product at a fixed rate r, or choose to stop the production. Each time the production is resumed, a setup cost must be paid. To prevent the backlog, which is not allowed, the manager can buy the product from outside vendors, paying a fixed order cost and a variable cost. There is also a linear inventory holding cost. The objective is to minimize the total ...
-
作者：NDOUTOUME, JL
摘要：This paper deals with the theory of first-order necessary conditions of optimality for nonsmooth control problems governed by variational inequalities. We present a general approach in which necessary conditions of first-order are obtained by means of differentiation tools based on epi-convergence of second-order differential quotients.
-
作者：DENG, XT; PAPADIMITRIOU, CH
作者单位：University of California System; University of California San Diego
摘要：We study from a complexity theoretic standpoint the various solution concepts arising in cooperative game theory. We use as a vehicle for this study a game in which the players are nodes of a graph with weights on the edges, and the value of a coalition is determined by the total weight of the edges contained in it. The Shapley value is always easy to compute. The core is easy to characterize when the game is convex, and is intractable (NP-complete) otherwise. Similar results are shown for the...
