-
作者：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...
-
作者：Dey, Santanu S.; Molinaro, Marco; Wang, Qianyi
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：In this paper, we study how well one can approximate arbitrary polytopes using sparse inequalities. Our motivation comes from the use of sparse cutting-planes in mixed-integer programing (MIP) solvers, since they help in solving the linear programs encountered during branch-&-bound more efficiently. However, how well can we approximate the integer hull by just using sparse cutting-planes? In order to understand this question better, given a polyope (e.g. the integer hull of a MIP), let be its ...
-
作者：Drusvyatskiy, D.; Ioffe, A. D.
作者单位：University of Washington; University of Washington Seattle; Technion Israel Institute of Technology
摘要：We show that quadratic growth of a semi-algebraic function is equivalent to strong metric subregularity of the subdifferential-a kind of stability of generalized critical points. In contrast, this equivalence can easily fail outside of the semi-algebraic setting. As a consequence, we derive necessary conditions and sufficient conditions for optimality in subdifferential terms.
-
作者：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...
