-
作者：Altman, E; Gaujal, B; Hordijk, A
作者单位：Inria; Universite de Lorraine; Leiden University - Excl LUMC; Leiden University
摘要：In this paper we investigate the properties of multimodular functions. In doing so we give elementary proofs for properties already established by Hajek and we generalize some of his results. In particular, we extend the relation between convexity and multimodularity to some convex subsets of Z(m). We also obtain general optimization results for average costs related to a sequence of multimodular functions rather than to a single function. Under this general context, we show that the expected ...
-
作者：Baveja, A; Srinivasan, A
作者单位：Rutgers University System; Rutgers University Camden; Rutgers University New Brunswick; Alcatel-Lucent; Lucent Technologies; AT&T
摘要：Given a network and a set of connection requests on it, we consider the maximum edge-disjoint paths and related generalizations and routing problems that arise in assigning paths for these requests. We present improved approximation algorithms and/or integrality gaps for all problems considered; the central theme of this work is the underlying multicommodity flow relaxation. Applications of these techniques to approximating families of packing integer programs are also presented.
-
作者：Solodov, MV; Svaiter, BF
摘要：We present a new Bregman-function-based algorithm which is a modification of the generalized proximal point method for solving the variational inequality problem with a maximal monotone operator. The principal advantage of the presented algorithm is that it allows a more constructive error tolerance criterion in solving the proximal point subproblems. Furthermore, we eliminate the assumption of pseudomonotonicity which was, until now, standard in proving convergence for paramonotone operators....
-
作者：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...
