-
作者：Burkard, RE; Deineko, VG; Woeginger, GJ
作者单位：Graz University of Technology; University of Warwick
摘要：Let D = (d(ij)) be the n x n distance matrix of a set of a cities {1, 2, ..., n}, and let Tbe a PQ-tree with node degree bounded by d that represents a set II(T) of permutations over {1, 2, ..., n}. We show how to compute for a in O(2(d)n(3)) time the shortest travelling salesman tour contained in IT(T). Our algorithm may be interpreted as a common generalization of the well-known Held and Karp dynamic programming algorithm for the TSP and of the dynamic programming algorithm for finding the s...
-
作者：Denuit, M; Lefèvre, C; Utev, S
作者单位：Universite Libre de Bruxelles; La Trobe University
摘要：Several new classes of discrete stochastic orderings are introduced for comparing discrete random variables that are valued in an arbitrary ordered finite grid of nonnegative points. These order relations correspond to particular cases of integral stochastic orderings which are generated by different classes of functions of convex/concave-type defined on the grid. They are natural extensions from equidistant to arbitrary grids of various orderings familiar in the literature. The main question ...
-
作者：Murota, K; Shioura, A
作者单位：Kyoto University; Sophia University
摘要：The concept of M-convex function, introduced by Murota (1996), isa quantitative generalization of the set of integral points in an integral base polyhedron as well as an extension of valuated matroid of Dress and Wenzel (1990). In this paper, we extend this concept to functions on generalized polymatroids with a view to providing a unified framework for efficiently solvable nonlinear discrete optimization problems.
-
作者：Philippe, F; Debs, G; Jaffray, JY
作者单位：Sorbonne Universite; Universite de Montpellier; Universite Paul-Valery
摘要：Properties of convex and monotone capacities of infinite order in Polish spaces are studied and used to justify the representation of certain situations of imprecise risk (imprecisely known probabilities) by lower probabilities, which are monotone of infinite order. Decision making with imprecise risk is then modeled, and linear utility theory is shown to be generalizable to the case of imprecise risk.
-
作者：Jiang, HY
作者单位：University of Melbourne
摘要：The nonlinear complementarity problem has been converted into a system of nonsmooth equations by means of Fischer-Burmeister functional, which may be called the Fischer-Burmeister equation. The local superlinear convergence of the generalized Newton method applied to the Fischer-Burmeister equation has been established under certain regularity assumptions. In contrast to the damped Newton method for systems of smooth equations, global convergence of the damped generalized Newton method for sys...
-
作者：Pisaruk, NN
作者单位：Belarusian State University
摘要：We study the mean cost cyclical game in a more general setting than that in Gurvitch et al. (1988) and Karzanow and Lebedev (1993). The game is played on a directed graph and generalizes the single source shortest. path problem. the minimum mean cycle problem (see Karp 1978), and the ergodic extension of matrix games (Moulin 1976). We prove the existence of a solution in uniform stationary strategies and present an algorithm for finding such optimal strategies. In fact, our algorithm is an ext...
-
作者：Pataki, G
作者单位：Columbia University
摘要：We derive some basic results on the geometry of semidefinite programming (SDP) and eigenvalue-optimization, i.e., the minimization of the sum of the k largest eigenvalues of a smooth matrix-valued function. We provide upper bounds on the rank of extreme matrices in SDPs, and the first theoretically solid explanation of a phenomenon of intrinsic interest in eigenvalue-optimization. In the spectrum of an optimal matrix, the kth and (k + 1)st largest eigenvalues tend to be equal and frequently ha...
-
作者：Heath, D; Resnick, S; Samorodnitsky, G
作者单位：Cornell University
摘要：On/off models are common inputs for a variety of communication network models as well as storage and inventory models. A stationary renewal process alternating periods of activity (active transmission, fluid buildup, etc) with periods of inactivity (silence, no transmission, inputs off, etc) induces a stationary indicator process which indicates if the system is active or not. Heavy tails for the on periods induces a covariance function for the indicator process which decreases slowly at a rat...
-
作者：Burkard, RE; Deineko, VG; Woeginger, GJ
作者单位：Graz University of Technology; University of Warwick
摘要：Let D = (d(ij)) be the n x n distance matrix of a set of n cities {1, 2,..., n}, and let T be a PQ-tree with node degree bounded by d that represents a set n(T) of permutations over {1, 2,..., n }. We show how to compute for D in O(2(d)n(3)) time the shortest travelling salesman tour contained in n(T). Our algorithm may be interpreted as a common generalization of the well-known Held and Karp dynamic programming algorithm for the TSP and of the dynamic programming algorithm for finding the sho...
-
作者：Teo, CP; Sethuraman, J
作者单位：National University of Singapore; Massachusetts Institute of Technology (MIT)
摘要：We study the classical stable marriage and stable roommates problems using a polyhedral approach. We propose a new LP formulation for the stable roommates problem, which has a feasible solution if and only if the underlying roommates problem has a stable matching. Furthermore, for certain special weight functions on the edges, we construct a a-approximation algorithm for the optimal stable roommates problem. Our technique exploits features of the geometry of fractional solutions of this formul...
