1-2期

最新文章

• Critical solutions of nonlinear equations: stability issues AI翻译
  作者：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...
• Ellipsoidal mixed-integer representability AI翻译
  作者：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...
• Approximating min-cost chain-constrained spanning trees: a reduction from weighted to unweighted problems AI翻译
  作者：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...
• 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.
• 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...
• 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...