-
作者：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.
-
作者：Ye, Jane J.
作者单位：University of Victoria
摘要：In this paper we consider the bilevel programming problem (BLPP), which is a sequence of two optimization problems where the constraint region of the upper-level problem is determined implicitly by the solution set to the lower-level problem. We extend well-known constraint qualifications for nonlinear programming problems such as the Abadie constraint qualification, the Kuhn-Tucker constraint qualification, the Zangwill constraint qualification, the Arrow-Hurwicz-Uzawa constraint qualificatio...
-
作者：Megow, Nicole; Uetz, Marc; Vredeveld, Tjark
作者单位：Technical University of Berlin; Maastricht University
摘要：We consider a model for scheduling under, uncertainty. In this model, we combine the main characteristics of online and stochastic scheduling in a simple and natural way. Job processing times are assumed to be stochastic, but in contrast to traditional stochastic scheduling models, we assume that jobs arrive online, and there is no knowledge about the jobs that will arrive in the future. The model incorporates both stochastic scheduling and online scheduling as a special case. The particular s...
-
作者：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.
-
作者：Mohebi, H; Rubinov, A
作者单位：Shahid Bahonar University of Kerman (SBUK); Federation University Australia
摘要：Necessary and sufficient conditions for a local minimum form a well-developed chapter of optimization theory. Determination of such conditions for the global minimum is a challenging problem. Useful conditions are currently known only for a few classes of nonconvex optimization problems. It is important to find different classes of problems for which the required conditions can be obtained. In this paper we examine one of these classes: the minimization of the distance to an arbitrary closed s...
-
作者：Arutyunov, A; Pereira, FL
作者单位：Peoples Friendship University of Russia; Universidade do Porto
摘要：In this article, we derive second-order necessary conditions of optimality for an abstract optimization problem with equality and inequality constraints and constraints in the form of an inclusion into a given closed set. An important feature is that our optimality conditions dispense with any a priori normality assumptions, such as Robinson's constraint qualification, and remain informative even for abnormal points. Moreover, our optimality conditions take into account the second-order effect...
-
作者：Bansal, N; Correa, JR; Kenyon, C; Sviridenko, M
作者单位：International Business Machines (IBM); IBM USA; Universidad Adolfo Ibanez; Brown University
摘要：We study the following packing problem: Given a collection of d-dimensional rectangles of specified sizes, pack them into the minimum number of unit cubes. We show that unlike the one-dimensional case, the two-dimensional packing problem cannot have an asymptotic polynomial time approximation scheme (APTAS), unless P = NP. On the positive side, we give an APTAS for the special case of packing d-dimensional cubes into the minimum number of unit cubes. Second, we give a polynomial time algorithm...
-
作者：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...
-
作者：Niño-Mora, J
作者单位：Universidad Carlos III de Madrid
摘要：This paper presents a framework grounded on convex optimization and economics ideas to solve by index policies problems of optimal dynamic allocation of effort to a discrete-state (finite or countable) binary-action (work/rest) semi-Markov restless bandit project, elucidating issues raised by previous work. Its contributions include: (i) the concept of a restless bandit's marginal productivity index (MPI), characterizing optimal policies relative to general cost and work measures; (ii) the cha...
