-
作者：Caprara, Alberto; Dell'Amico, Mauro; Diaz-Diaz, Jose Carlos; Iori, Manuel; Rizzi, Romeo
作者单位：Universita di Modena e Reggio Emilia; University of Verona
摘要：It is well known that the gap between the optimal values of bin packing and fractional bin packing, if the latter is rounded up to the closest integer, is almost always null. Known counterexamples to this for integer input values involve fairly large numbers. Specifically, the first one was derived in 1986 and involved a bin capacity of the order of a billion. Later in 1998 a counterexample with a bin capacity of the order of a million was found. In this paper we show a large number of counter...
-
作者：Gouveia, Luis; Leitner, Markus; Ljubic, Ivana
作者单位：Universidade de Lisboa; University of Vienna; Technische Universitat Wien
摘要：In this article, we introduce the two-level diameter constrained spanning tree problem (2-DMSTP), which generalizes the classical DMSTP by considering two sets of nodes with different latency requirements. We first observe that any feasible solution to the 2-DMSTP can be viewed as a DMST that contains a diameter constrained Steiner tree. This observation allows us to prove graph theoretical properties related to the centers of each tree which are then exploited to develop mixed integer program...
-
作者：Wright, Stephen J.
作者单位：University of Wisconsin System; University of Wisconsin Madison
摘要：Coordinate descent algorithms solve optimization problems by successively performing approximate minimization along coordinate directions or coordinate hyperplanes. They have been used in applications for many years, and their popularity continues to grow because of their usefulness in data analysis, machine learning, and other areas of current interest. This paper describes the fundamentals of the coordinate descent approach, together with variants and extensions and their convergence propert...
-
作者：Qian, Jiawei; Schalekamp, Frans; Williamson, David P.; van Zuylen, Anke
作者单位：William & Mary; Cornell University
摘要：In this paper, we study the integrality gap of the subtour LP relaxation for the traveling salesman problem in the special case when all edge costs are either 1 or 2. For the general case of symmetric costs that obey triangle inequality, a famous conjecture is that the integrality gap is 4/3. Little progress towards resolving this conjecture has been made in 30 years. We conjecture that when all edge costs , the integrality gap is 10/9. We show that this conjecture is true when the optimal sub...
-
作者：Bonami, Pierre; Lodi, Andrea; Tramontani, Andrea; Wiese, Sven
作者单位：University of Bologna
摘要：In this paper we review the relevant literature on mathematical optimization with logical implications, i.e., where constraints can be either active or disabled depending on logical conditions to hold. In the case of convex functions, the theory of disjunctive programming allows one to formulate these logical implications as convex nonlinear programming problems in a space of variables lifted with respect to its original dimension. We concentrate on the attempt of avoiding the issue of dealing...
-
作者：Vegh, Laszlo A.; von Stengel, Bernhard
作者单位：University of London; London School Economics & Political Science; University of London; London School Economics & Political Science
摘要：This paper presents oriented pivoting systems as an abstract framework for complementary pivoting. It gives a unified simple proof that the endpoints of complementary pivoting paths have opposite sign. A special case are the Nash equilibria of a bimatrix game at the ends of Lemke-Howson paths, which have opposite index. For Euler complexes or oiks, an orientation is defined which extends the known concept of oriented abstract simplicial manifolds. Ordered room partitions for a family of orient...
-
作者：Avis, David; Tiwary, Hans Raj
作者单位：McGill University; Universite de Montreal; McGill University; Kyoto University; Universite Libre de Bruxelles
摘要：In this paper we extend recent results of Fiorini et al. on the extension complexity of the cut polytope and related polyhedra. We first describe a lifting argument to show exponential extension complexity for a number of NP-complete problems including subset-sum and three dimensional matching. We then obtain a relationship between the extension complexity of the cut polytope of a graph and that of its graph minors. Using this we are able to show exponential extension complexity for the cut po...
-
作者：Basu, Amitabh; Conforti, Michele; Di Summa, Marco
作者单位：Johns Hopkins University; University of Padua
摘要：The cutting-plane approach to integer programming was initiated more than 40 years ago: Gomory introduced the corner polyhedron as a relaxation of a mixed integer set in tableau form and Balas introduced intersection cuts for the corner polyhedron. This line of research was left dormant for several decades until relatively recently, when a paper of Andersen, Louveaux, Weismantel and Wolsey generated renewed interest in the corner polyhedron and intersection cuts. Recent developments rely on to...
-
作者：Couetoux, Basile; Davis, James M.; Williamson, David P.
作者单位：Aix-Marseille Universite; Cornell University
摘要：We consider a class of graph problems introduced in a paper of Goemans and Williamson that involve finding forests of minimum edge cost. This class includes a number of location/routing problems; it also includes a problem in which we are given as input a parameter , and want to find a forest such that each component has at least vertices. Goemans and Williamson gave a 2-approximation algorithm for this class of problems. We give an improved 3/2-approximation algorithm.
-
作者：Gouveia, Joo; Robinson, Richard Z.; Thomas, Rekha R.
作者单位：Universidade de Coimbra; University of Washington; University of Washington Seattle
摘要：We present various worst-case results on the positive semidefinite (psd) rank of a nonnegative matrix, primarily in the context of polytopes. We prove that the psd rank of a generic -dimensional polytope with vertices is at least improving on previous lower bounds. For polygons with vertices, we show that psd rank cannot exceed which in turn shows that the psd rank of a matrix of rank three is at most . In general, a nonnegative matrix of rank has psd rank at least and we pose the problem of d...
