-
作者：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 ...
-
作者：Shigeno, M
作者单位：University of Tsukuba
摘要：This paper deals with a generalized maximum flow problem with concave gains, which is a nonlinear network optimization problem. Optimality conditions and an algorithm for this problem are presented. The optimality conditions are extended from the corresponding results for the linear gain case. The algorithm is based on the scaled piecewise linear approximation and on the fat path algorithm described by Goldberg, Plotkin and Tardos for linear gain cases. The proposed algorithm solves a problem ...
-
作者：Ben-Ameur, W; Neto, J
作者单位：IMT - Institut Mines-Telecom; Institut Polytechnique de Paris; Telecom SudParis
摘要：In order to solve linear programs with a large number of constraints, constraint generation techniques are often used. In these algorithms, a relaxation of the formulation containing only a subset of the constraints is first solved. Then a separation procedure is called which adds to the relaxation any inequality of the formulation that is violated by the current solution. The process is iterated until no violated inequality can be found. In this paper, we present a separation procedure that u...
-
作者：Malik, U; Jaimoukha, IM; Halikias, GD; Gungah, SK
作者单位：Imperial College London; City St Georges, University of London
摘要：Consider the semidefinite relaxation (SDR) of the quadratic integer program (QIP): gamma := max {x(T) Qx : x is an element of {-1, 1}(n)} <= min {trace(D) : D - Q greater than or similar to 0} =: (gamma) over bar where Q is a given symmetric matrix and D is diagonal. We consider the SDR gap (gamma) over bar gamma. We establish the uniqueness of the SDR solution and prove that gamma = (gamma) over bar if and only if gamma(r) := n(-1) max {x(T) VVT x : x is an element of {-1, 1}(n)} = 1 where V ...
-
作者：Chubanov, S; Kovalyov, MY; Pesch, E
作者单位：Belarusian State University; Universitat Siegen; National Academy of Sciences of Belarus (NASB); United Institute of Informatics Problems of the National Academy of Sciences of Belarus
摘要：We present a fully polynomial time approximation scheme (FPTAS) for a capacitated economic lot-sizing problem with a monotone cost structure. An FPTAS delivers a solution with a given relative error epsilon in time polynomial in the problem size and in 1/epsilon. Such a scheme was developed by van Hoesel and Wagelmans [8] for a capacitated economic lot-sizing problem with monotone concave (convex) production and backlogging cost functions. We omit concavity and convexity restrictions. Furtherm...
-
作者：Jansen, K
作者单位：University of Kiel
摘要：We propose an approximation algorithm for, the general max-min resource sharing problem with M nonnegative concave constraints on a convex set B. The algorithm is based on a Lagrangian decomposition method and it uses a c-approximation algorithm (called approximate block solver) for a simpler maximization problem over the convex set B. We show that our algorithm achieves within O( M(1nM + is an element of(-2) 1n is an element of(-1))) iterations or calls to the approximate block solver a solut...
