2018

最新文章

• Least cost influence propagation in (social) networks AI翻译
  作者：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...
• Semidefinite and linear programming integrality gaps for scheduling identical machines AI翻译
  作者：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...
• Polyhedral results on the stable set problem in graphs containing even or odd pairs AI翻译
  作者：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.
• Piecewise static policies for two-stage adjustable robust linear optimization AI翻译
  作者：El Housni, Omar; Goyal, Vineet
  作者单位：Columbia University
  摘要：In this paper, we consider two-stage adjustable robust linear optimization problems under uncertain constraints and study the performance of piecewise static policies. These are a generalization of static policies where we divide the uncertainty set into several pieces and specify a static solution for each piece. We show that in the worst-case, there is no piecewise static policy with a polynomial number of pieces that has a significantly better performance than an optimal static policy. This...
• L∞ estimates on trajectories confined to a closed subset, for control systems with bounded time variation AI翻译
  作者：Bettiol, Piernicola; Vinter, Richard B.
  作者单位：Universite de Bretagne Occidentale; Imperial College London
  摘要：The term 'distance estimate' for state constrained control systems refers to an estimate on the distance of an arbitrary state trajectory from the subset of state trajectories that satisfy a given state constraint. Distance estimates have found widespread application in state constrained optimal control. They have been used to establish regularity properties of the value function, to establish the non-degeneracy of first order conditions of optimality, and to validate the characterization of t...
• A Short Proof of the Sticky Face Lemma AI翻译
  作者：Robinson, Stephen M.
  作者单位：University of Wisconsin System; University of Wisconsin Madison
  摘要：The sticky face lemma describes the local behavior of the inverse of the normal-cone operator of a polyhedral convex set. This inverse, when applied to a vector, produces a face of the set. The lemma says that small perturbations of the vector produce only subfaces of the original face. This property is useful in analyzing variational analysis and optimization problems whose underlying sets are convex and polyhedral.
• Polynomial combinatorial algorithms for skew-bisubmodular function minimization AI翻译
  作者：Fujishige, Satoru; Tanigawa, Shin-ichi
  作者单位：Kyoto University
  摘要：Huber et al. (SIAM J Comput 43: 1064-1084, 2014) introduced a concept of skew bisubmodularity, as a generalization of bisubmodularity, in their complexity dichotomy theorem for valued constraint satisfaction problems over the three-value domain, and Huber and Krokhin (SIAM J Discrete Math 28: 1828-1837, 2014) showed the oracle tractability of minimization of skew-bisubmodular functions. Fujishige et al. (Discrete Optim 12: 1-9, 2014) also showed a min-max theorem that characterizes the skew-bi...
• Mixed integer reformulations of integer programs and the affine TU-dimension of a matrix AI翻译
  作者：Bader, Jorg; Hildebrand, Robert; Weismantel, Robert; Zenklusen, Rico
  作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich; International Business Machines (IBM); IBM USA
  摘要：We study the reformulation of integer linear programs by means of a mixed integer linear program with fewer integer variables. Such reformulations can be solved efficiently with mixed integer linear programming techniques. We exhibit examples that demonstrate how integer programs can be reformulated using far fewer integer variables. To this end, we introduce a generalization of total unimodularity called the affine TU-dimension of a matrix and study related theory and algorithms for determini...
• Representative functions of maximally monotone operators and bifunctions AI翻译
  作者：Bianchi, Monica; Hadjisavvas, Nicolas; Pini, Rita
  作者单位：Catholic University of the Sacred Heart; King Fahd University of Petroleum & Minerals; University of Milano-Bicocca
  摘要：The aim of this paper is to show that every representative function of a maximally monotone operator is the Fitzpatrick transform of a bifunction corresponding to the operator. In fact, for each representative function of the operator, there is a family of equivalent saddle functions (i.e., bifunctions which are concave in the first and convex in the second argument) each of which has as Fitzpatrick transform. In the special case where is the Fitzpatrick function of the operator, the family of...
• Sparsest cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem AI翻译
  作者：Baiou, Mourad; Barahona, Francisco
  作者单位：Centre National de la Recherche Scientifique (CNRS); International Business Machines (IBM); IBM USA
  摘要：We study the sparsest cut problem when the capacity-demand graph is planar, and give a combinatorial polynomial algorithm. In this type of graphs there is an edge for each positive capacity and also an edge for each positive demand. We extend this result to graphs with no K5 minor. We also show how to find a maximum concurrent flow in these two cases. We also prove that the sparsest cut problem is NP-hard if we only impose that the capacity-demand graph has no K6 minor. We use ideas that had...