-
作者：Zhang, Jiawei
作者单位：New York University
摘要：We propose a quasi-greedy algorithm for approximating the classical uncapacitated 2-level facility location problem (2-LFLP). Our algorithm, unlike the standard greedy algorithm, selects a sub-optimal candidate at each step. It also relates the minimization 2-LFLP problem, in an interesting way, to the maximization version of the single level facility location problem. Another feature of our algorithm is that it combines the technique of randomized rounding with that of dual fitting. This new ...
-
作者：Fukasawa, R; Longo, H; Lysgaard, J; de Aragao, MP; Reis, M; Uchoa, E; Werneck, RF
作者单位：Universidade Federal Fluminense; Universidade Federal de Goias; Aarhus University; Pontificia Universidade Catolica do Rio de Janeiro; Princeton University
摘要：The best exact algorithms for the Capacitated Vehicle Routing Problem (CVRP) have been based on either branch-and-cut or Lagrangean relaxation/column generation. This paper presents an algorithm that combines both approaches: it works over the intersection of two polytopes, one associated with a traditional Lagrangean relaxation over q-routes, the other defined by bound, degree and capacity constraints. This is equivalent to a linear program with exponentially many variables and constraints th...
-
作者：Adler, I; Cottle, RW; Verma, S
作者单位：University of California System; University of California Berkeley; Stanford University
摘要：In this paper, we establish a significant matrix class inclusion that seems to have been overlooked in the literature of the linear complementarity problem. We show that P-*,P- the class of sufficient matrices, is a subclass of L. In the course of demonstrating this inclusion, we introduce other new matrix classes that forge interesting new connections between known matrix classes.
-
作者：Letchford, AN; Salazar-González, JJ
作者单位：Lancaster University; Universidad de la Laguna
摘要：A variety of integer programming formulations have been proposed for Vehicle Routing Problems (VRPs), including the so-called two- and three-index formulations, the set partitioning formulation, and various formulations based on extra variables representing the flow of one or more commodities. Until now, there has not been a systematic study of how these formulations relate to each other. An exception is a paper of Luis Gouveia, which shows that a one-commodity flow formulation of Gavish and G...
-
作者：Cottle, RW
作者单位：Stanford University
摘要：Mathematical programming owes much to George B. Dantzig who passed away on May 13, 2005 at the age of 90. This article is a tribute to this legendary pioneer and a very brief review of his extensive and enduring contributions to our field.
-
作者：Sherali, Hanif D.; Zhu, Xiaomei
作者单位：Virginia Polytechnic Institute & State University
摘要：In this paper, we propose a decomposition-based branch-and-bound (DBAB) algorithm for solving two-stage stochastic programs having mixed-integer first- and second-stage variables. A modified Benders' decomposition method is developed, where the Benders' subproblems define lower bounding second-stage value functions of the first-stage variables that are derived by constructing a certain partial convex hull representation of the two-stage solution space. This partial convex hull is sequentially ...
-
作者：Van der Laan, G.; Talman, D. A. J. J.; Yang, Z.
作者单位：Vrije Universiteit Amsterdam; Tinbergen Institute; Vrije Universiteit Amsterdam; Tilburg University; Tilburg University; Yokohama National University
摘要：In this paper we present two theorems on the existence of a discrete zero point of a function from the n-dimensional integer lattice Z(n) to the n-dimensional Euclidean space R-n. The theorems differ in their boundary conditions. For both theorems we give a proof using a combinatorial lemma and present a constructive proof based on a simplicial algorithm that finds a discrete zero point within a finite number of steps.
-
作者：d'Aspremont, A; El Ghaoui, L
作者单位：Princeton University; University of California System; University of California Berkeley
摘要：We consider the problem of computing upper and lower bounds on the price of an European basket call option, given prices on other similar options. Although this problem is hard to solve exactly in the general case, we show that in some instances the upper and lower bounds can be computed via simple closed-form expressions, or linear programs. We also introduce an efficient linear programming relaxation of the general problem based on an integral transform interpretation of the call price funct...
-
作者：Arora, S; Karakostas, G
作者单位：Princeton University; McMaster University
摘要：For any epsilon > 0 we give a (2 + epsilon)-approximation algorithm for the problem of finding a minimum tree spanning any k vertices in a graph (k-MST), improving a 3-approximation algorithm by Garg [10]. As in [10] the algorithm extends to a (2 + epsilon)-approximation algorithm for the minimum tour that visits any k vertices, provided the edge costs satisfy the triangle inequality.
-
作者：Nie, JW; Demmel, J; Sturmfels, B
作者单位：University of California System; University of California Berkeley; University of California System; University of California Berkeley
摘要：A method is proposed for finding the global minimum of a multivariate polynomial via sum of squares (SOS) relaxation over its gradient variety. That variety consists of all points where the gradient is zero and it need not be finite. A polynomial which is nonnegative on its gradient variety is shown to be SOS modulo its gradient ideal, provided the gradient ideal is radical or the polynomial is strictly positive on the real gradient variety. This opens up the possibility of solving previously ...
