-
作者：Dyer, Martin; Stougie, Leen
作者单位：University of Leeds; Eindhoven University of Technology; Centrum Wiskunde & Informatica (CWI)
-
作者：Morris, Walter D., Jr.
作者单位：George Mason University
摘要：We use recent results on algorithms for Markov decision problems to show that a canonical form for a matrix with the generalized P-property can be computed, in some important cases, by a strongly polynomial algorithm.
-
作者：Lu, Zhaosong; Xiao, Lin
作者单位：Simon Fraser University; Microsoft
摘要：In this paper we analyze the randomized block-coordinate descent (RBCD) methods proposed in Nesterov (SIAM J Optim 22(2):341-362, 2012), Richtarik and Taka (Math Program 144(1-2):1-38, 2014) for minimizing the sum of a smooth convex function and a block-separable convex function, and derive improved bounds on their convergence rates. In particular, we extend Nesterov's technique developed in Nesterov (SIAM J Optim 22(2):341-362, 2012) for analyzing the RBCD method for minimizing a smooth conve...
-
作者：Nesterov, Yu
作者单位：Universite Catholique Louvain
摘要：In this paper, we present new methods for black-box convex minimization. They do not need to know in advance the actual level of smoothness of the objective function. Their only essential input parameter is the required accuracy of the solution. At the same time, for each particular problem class they automatically ensure the best possible rate of convergence. We confirm our theoretical results by encouraging numerical experiments, which demonstrate that the fast rate of convergence, typical f...
-
作者：Gouveia, Joo; Parrilo, Pablo A.; Thomas, Rekha R.
作者单位：Universidade de Coimbra; Massachusetts Institute of Technology (MIT); University of Washington; University of Washington Seattle
摘要：In this paper we show how to construct inner and outer convex approximations of a polytope from an approximate cone factorization of its slack matrix. This provides a robust generalization of the famous result of Yannakakis that polyhedral lifts of a polytope are controlled by (exact) nonnegative factorizations of its slack matrix. Our approximations behave well under polarity and have efficient representations using second order cones. We establish a direct relationship between the quality of...
-
作者：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...
-
作者：Angulo, Alejandro; Espinoza, Daniel; Palma, Rodrigo
作者单位：Universidad de Chile; Universidad de Chile
摘要：In this paper, we consider the semi-continuous knapsack problem with generalized upper bound constraints on binary variables. We prove that generalized flow cover inequalities are valid in this setting and, under mild assumptions, are facet-defining inequalities for the entire problem. We then focus on simultaneous lifting of pairs of variables. The associated lifting problem naturally induces multidimensional lifting functions, and we prove that a simple relaxation in a restricted domain is a...
-
作者：Kilinc-Karzan, Fatma; Yildiz, Sercan
作者单位：Carnegie Mellon University
摘要：Balas introduced disjunctive cuts in the 1970s for mixed-integer linear programs. Several recent papers have attempted to extend this work to mixed-integer conic programs. In this paper we study the structure of the convex hull of a two-term disjunction applied to the second-order cone and develop a methodology to derive closed-form expressions for convex inequalities describing the resulting convex hull. Our approach is based on first characterizing the structure of undominated valid linear i...
-
作者：Shioura, Akiyoshi; Shakhlevich, Natalia V.; Strusevich, Vitaly A.
作者单位：Tohoku University; University of Leeds; University of Greenwich
摘要：In this paper we present a decomposition algorithm for maximizing a linear function over a submodular polyhedron intersected with a box. Apart from this contribution to submodular optimization, our results extend the toolkit available in deterministic machine scheduling with controllable processing times. We demonstrate how this method can be applied to developing fast algorithms for minimizing total compression cost for preemptive schedules on parallel machines with respect to given release d...
