-
作者：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...
-
作者：Burkard, RE; Deineko, VG; Woeginger, GJ
作者单位：Graz University of Technology; University of Warwick
摘要：Let D = (d(ij)) be the n x n distance matrix of a set of a cities {1, 2, ..., n}, and let Tbe a PQ-tree with node degree bounded by d that represents a set II(T) of permutations over {1, 2, ..., n}. We show how to compute for a in O(2(d)n(3)) time the shortest travelling salesman tour contained in IT(T). Our algorithm may be interpreted as a common generalization of the well-known Held and Karp dynamic programming algorithm for the TSP and of the dynamic programming algorithm for finding the s...
-
作者：Murota, K; Shioura, A
作者单位：Kyoto University; Sophia University
摘要：The concept of M-convex function, introduced by Murota (1996), isa quantitative generalization of the set of integral points in an integral base polyhedron as well as an extension of valuated matroid of Dress and Wenzel (1990). In this paper, we extend this concept to functions on generalized polymatroids with a view to providing a unified framework for efficiently solvable nonlinear discrete optimization problems.
