-
作者：Schäl, M
作者单位：University of Bonn
摘要：The price of stocks is modelled by a discrete-time, square-integrable, vector-valued process X. No further boundedness condition on X is imposed. Contingent claims X are described by square-integrable random variables. One looks for values nu of the initial wealth nu that allow for super-hedging H by some portfolio plan. In several cases, the smallest value nu is known to coincide with the maximal expectation of H under equivalent martingale measures. Here, within an L-2-framework, another suf...
-
作者：Deng, XT; Ibaraki, T; Nagamochi, H
作者单位：City University of Hong Kong; Kyoto University
摘要：We discuss an integer programming formulation for a class of cooperative games. We focus on algorithmic aspects of the core, one of the most important solution concepts in cooperative game theory. Central to our study is a simple (but very useful) observation that the core for this class is nonempty if and only if an associated linear program has an integer optimal solution. Based on this, we study the computational complexity and algorithms to answer important questions about the cores of var...
-
作者：Zervos, M
作者单位：Newcastle University - UK
摘要：The problem of strong consistency of sequences of optimal solutions to stochastic optimization problems is considered. This problem is related to a large number of applications including Bayesian decision problems and Monte Carlo simulations, as well as a number of statistical methodologies such as maximum likelihood estimation. The theory of epiconvergence being a framework within which such results can be established, the epiconvergence of the performance criteria of a sequence of stochastic...
-
作者：Fleischer, L; Tardos, É
作者单位：Columbia University; Cornell University
摘要：Traveling Salesman Problem (TSP) is a benchmark problem in combinatorial optimization. It was one of the very first problems used for developing and testing approaches to solving large integer programs. including cutting plane algorithms and branch-and-cut algorithms. Much of the research in this area has been focused on finding new classes of facets for the TSP polytope and much less attention has been paid to algorithms for separating from these classes of facets. In this paper, we consider ...
-
作者：Anstreicher, KM
作者单位：University of Iowa
摘要：Let C subset of R-n be a convex set. We assume that \\x\\(infinity) less than or equal to 1 for all x is an element of C, and that C contains a ball of radius 1/R. For x is an element of R-n, r is an element of R, and B an n X n symmetric positive definite matrix, let E(x, B, r) = {y\(y - x)B-T(y - x) less than or equal to r(2)}. A beta-rounding of C is an ellipsoid E(x, B, r) such that E(x, B, r/beta) subset of C subset of E(x, B, r). In the case that C is characterized by a separation oracle...
-
作者：De Meyer, B; Rosenberg, D
作者单位：Universite Catholique Louvain; Universite Paris 13
摘要：We give an alternative proof of a theorem of Aumann and Maschler that characterizes the limit of the values of finitely repeated games with lack of information on one side as the concavification of the value of the game where none of the players has any information. Our proof is based on Fenchel duality techniques.
-
作者：Glass, CA; Gupta, JND; Potts, CN
作者单位：University of Southampton; Ball State University
摘要：This paper considers the no-wait scheduling of n jobs in a two-machine flow shop, where some jobs require processing on the first machine only. The objective is to minimize the maximum completion time, or makespan. In view of its NP-hardness, we propose and analyze heuristic algorithms. Our main result is an O(n log n)-time heuristic which generates a schedule with makespan no more than 4/3 times that of an optimal schedule. This heuristic solves optimally the subproblem involving the jobs wit...
-
作者：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.
