-
作者：Guerraggio, Angelo; Luc, Dinh The
作者单位：Bocconi University; Avignon Universite
摘要：We study maximal points in a locally convex space partially ordered by a convex cone with a bounded base. Properly maximal points are defined and compared with other concepts of efficiency. Existence and density theorems are given which unify and generalize several results known in recent literature. Particular attention is paid on properly maximal points in a product space which has an interesting application in obtaining a multiplier rule for convex set-valued problems in a general setting.
-
作者：Bayraktar, Erhan; Dayanik, Savas
作者单位：University of Michigan System; University of Michigan; Princeton University
摘要：We solve the Poisson disorder problem when the delay is penalized exponentially. Our objective is to detect as quickly as possible the unobservable time of the change (or disorder) in the intensity of a Poisson process. The disorder time delimits two different regimes in which one employs distinct strategies (e.g., investment, advertising, manufacturing). We seek a stopping rule that minimizes the frequency of false alarms and an exponential (unlike previous formulations, which use a linear) c...
-
作者：Calvin, James M.; Nakayama, Marvin K.
作者单位：New Jersey Institute of Technology
摘要：We describe an extension procedure for constructing new standardized time series procedures from existing ones. The approach is based on averaging over sample paths obtained by permuting path segments. Analytical and empirical results indicate that permuting improves standardized time series methods. We compare permuting to an alternative extension procedure known as batching. We demonstrate the permuting method by applying it to estimators based on the maximum and the area of a normalized path.
-
作者：Levi, Retsef; Roundy, Robin O.; Shmoys, David B.
作者单位：International Business Machines (IBM); IBM USA; Cornell University; Cornell University; Cornell University
摘要：We consider several classical models in deterministic inventory theory: the single-item lot-sizing problem, the joint replenishment problem, and the multistage assembly problem. These inventory models have been studied extensively, and play a fundamental role in broader planning issues, such as the management of supply chains. For each of these problems, we wish to balance the cost of maintaining surplus inventory for future demand against the cost of replenishing inventory more frequently. Fo...
-
作者：Kalai, Adam Tauman; Vempala, Santosh
作者单位：Toyota Technological Institute - Chicago; Massachusetts Institute of Technology (MIT)
摘要：We apply the method known as simulated annealing to the following problem in convex optimization: Minimize a linear function over an arbitrary convex set, where the convex set is specified only by a membership oracle. Using distributions from the Boltzmann-Gibbs family leads to an algorithm that needs only O*(root n) phases for instances in R-n. This gives an optimization algorithm that makes O*(n(4.5)) calls to the membership oracle, in the worst case, compared to the previous best guarantee ...
-
作者：Caldentey, Rene; Haugh, Martin
作者单位：New York University; Columbia University
摘要：We consider the problem of dynamically hedging the profits of a corporation when these profits are correlated with returns in the financial markets. In particular, we consider the general problem of simultaneously optimizing over both the operating policy and the hedging strategy of the corporation. We discuss how different informational assumptions give rise to different types of hedging and solution techniques. Finally, we solve some problems commonly encountered in operations management to ...
-
作者：Charikar, Moses; Goemans, Michel X.; Karloff, Howard
作者单位：Princeton University; Massachusetts Institute of Technology (MIT); AT&T
摘要：We improve the lower bound on the integrality ratio of the Held-Karp bound for asymmetric TSP with triangle inequality from 4/3 to 2.
-
作者：Bansal, Nikhil; Kimbrel, Tracy; Sviridenko, Maxim
作者单位：International Business Machines (IBM); IBM USA
摘要：We consider randomized algorithms for the preemptive job shop problem, or equivalently, the case in which all operations have unit length. We give an a-approximation for the case of two machines where alpha < 1.45, an improved approximation ratio of O(log m/log log m) for an arbitrary number m of machines, and the first (2 + epsilon) -approximation for a constant number of machines. The first result is via an approximation algorithm for a string matching problem that is of independent interest.
-
作者：Van Roy, Benjamin
作者单位：Stanford University
摘要：We consider approximate value iteration with a parameterized approximator in which the state space is partitioned and the optimal cost-to-go function over each partition is approximated by a constant. We establish performance loss bounds for policies derived from approximations associated with fixed points. These bounds identify benefits to using invariant distributions of appropriate policies as projection weights. Such projection weighting relates to what is done by temporal-difference learn...
-
作者：Bietenhader, Thomas; Okamoto, Yoshio
作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich; Toyohashi University of Technology
摘要：In cooperative game theory, a characterization of games with stable cores is known as one of the most notorious open problems. We study this problem for a special case of the minimum coloring games, introduced by Deng et al. [10], which arise from a cost allocation problem when the players are involved in conflict. In this paper, we show that the minimum coloring game on a perfect graph has a stable core if and only if every vertex of the graph belongs to a maximum clique. We also consider the...
