-
作者：van Zuylen, Anke
作者单位：William & Mary
摘要：We show improved approximation guarantees for the traveling salesman problem on cubic bipartite graphs and cubic graphs. For connected cubic bipartite graphs with n nodes, we improve on recent results of Karp and Ravi by giving a local improvement algorithm that finds a tour of length at most 5/ 4n -2. For 2-connected cubic graphs, we show that the techniques of Momke and Svensson can be combined with the techniques of Correa, Larre and Soto, to obtain a tour of length at most ('4/ 3 -1/ 8754...
-
作者：Izmailov, A. F.; Kurennoy, A. S.; Solodov, M. V.
作者单位：Lomonosov Moscow State University; Peoples Friendship University of Russia; Derzhavin Tambov State University; Instituto Nacional de Matematica Pura e Aplicada (IMPA)
摘要：It is known that when the set of Lagrange multipliers associated with a stationary point of a constrained optimization problem is not a singleton, this set may contain so-called critical multipliers. This special subset of Lagrange multipliers defines, to a great extent, stability pattern of the solution in question subject to parametric perturbations. Criticality of a Lagrange multiplier can be equivalently characterized by the absence of the local Lipschitzian error bound in terms of the nat...
-
作者：Combettes, Patrick L.; Salzo, Saverio; Villa, Silvia
作者单位：North Carolina State University; Istituto Italiano di Tecnologia - IIT; Polytechnic University of Milan
摘要：We investigate the modeling and the numerical solution of machine learning problems with prediction functions which are linear combinations of elements of a possibly infinite dictionary of functions. We propose a novel flexible composite regularization model, which makes it possible to incorporate various priors on the coefficients of the prediction function, including sparsity and hard constraints. We show that the estimators obtained by minimizing the regularized empirical risk are consisten...
-
作者：Del Pia, Alberto; Poskin, Jeffrey
作者单位：University of Wisconsin System; University of Wisconsin Madison; University of Wisconsin System; University of Wisconsin Madison
摘要：Representability results for mixed-integer linear systems play a fundamental role in optimization since they give geometric characterizations of the feasible sets that can be formulated by mixed-integer linear programming. We consider a natural extension of mixed-integer linear systems obtained by adding just one ellipsoidal inequality. The set of points that can be described, possibly using additional variables, by these systems are called ellipsoidal mixed-integer representable. In this work...
-
作者：Linhares, Andre; Swamy, Chaitanya
作者单位：University of Waterloo
摘要：We study the min-cost chain-constrained spanning-tree (MCCST) problem: find a min-cost spanning tree in a graph subject to degree constraints on a nested family of node sets. We devise the first polytime algorithm that finds a spanning tree that (i) violates the degree constraints by at most a constant factor and (ii) whose cost is within a constant factor of the optimum. Previously, only an algorithm for unweighted CCST was known (Olver and Zenklusen in Proceedings of the 16th IPCO, pp 324-33...
-
作者：Cozad, Alison; Sahinidis, Nikolaos V.
作者单位：Carnegie Mellon University; Exxon Mobil Corporation
摘要：Symbolic regression methods generate expression trees that simultaneously define the functional form of a regression model and the regression parameter values. As a result, the regression problem can search many nonlinear functional forms using only the specification of simple mathematical operators such as addition, subtraction, multiplication, and division, among others. Currently, state-of-the-art symbolic regression methods leverage genetic algorithms and adaptive programming techniques. G...
-
作者：Zhang, Chong; Minh Pham; Fu, Sheng; Liu, Yufeng
作者单位：University of Waterloo; University of Virginia; Chinese Academy of Sciences; University of Chinese Academy of Sciences, CAS; University of North Carolina; University of North Carolina Chapel Hill; University of North Carolina School of Medicine
摘要：The support vector machine (SVM) is one of the most popular classification methods in the machine learning literature. Binary SVM methods have been extensively studied, and have achieved many successes in various disciplines. However, generalization to multicategory SVM (MSVM) methods can be very challenging. Many existing methods estimate k functions for k classes with an explicit sum-to-zero constraint. It was shown recently that such a formulation can be suboptimal. Moreover, many existing ...
-
作者：Fischetti, Matteo; Kahr, Michael; Leitner, Markus; Monaci, Michele; Ruthmair, Mario
作者单位：University of Padua; University of Vienna; University of Bologna
摘要：Influence maximization problems aim to identify key players in (social) networks and are typically motivated from viral marketing. In this work, we introduce and study the Generalized Least Cost Influence Problem (GLCIP) that generalizes many previously considered problem variants and allows to overcome some of their limitations. A formulation that is based on the concept of activation functions is proposed together with strengthening inequalities. Exact and heuristic solution methods are deve...
-
作者：Kurpisz, Adam; Mastrolilli, Monaldo; Mathieu, Claire; Moemke, Tobias; Verdugo, Victor; Wiese, Andreas
作者单位：Universita della Svizzera Italiana; Universite PSL; Ecole Normale Superieure (ENS); Centre National de la Recherche Scientifique (CNRS); CNRS - Institute for Information Sciences & Technologies (INS2I); Saarland University; Universidad de Chile; Max Planck Society
摘要：Sherali and Adams (SIAM J Discrete Math 3: 411-430, 1990) and Lovasz and Schrijver (SIAM J Optim 1: 166-190, 1991) developed systematic procedures to construct the hierarchies of relaxations known as lift-and-project methods. They have been proven to be a strong tool for developing approximation algorithms, matching the best relaxations known for problems like Max-Cut and Sparsest-Cut. In this work we provide lower bounds for these hierarchies when applied over the configuration LP for the pro...
-
作者：Witt, Jonas T.; Luebbecke, Marco E.; Reed, Bruce
作者单位：RWTH Aachen University; Centre National de la Recherche Scientifique (CNRS); Universite Cote d'Azur; Instituto Nacional de Matematica Pura e Aplicada (IMPA)
摘要：Even and odd pairs are important tools in the study of perfect graphs and were instrumental in the proof of the Strong Perfect Graph Theorem. We suggest that such pairs impose a lot of structure also in arbitrary, not just perfect graphs. To this end, we show that the presence of even or odd pairs in graphs imply a special structure of the stable set polytope. In fact, we give a polyhedral characterization of even and odd pairs.
