1-2期

最新文章

• Integer round-up property for the chromatic number of some h-perfect graphs AI翻译
  作者：Benchetrit, Yohann
  作者单位：Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS); Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS)
  摘要：We prove that every h-perfect line graph and every t-perfect claw-free graph G has the integer round-up property for the chromatic number: for every non-negative integral weight function c on the vertices of G, the weighted chromatic number of (G, c) can be obtained by rounding up its fractional relaxation. As a corollary, we obtain that the weighted chromatic number can be computed in polynomial-time for these graphs. Finally, we show a new example of a graph operation which preserves the int...
• Polyhedral aspects of score equivalence in Bayesian network structure learning AI翻译
  作者：Cussens, James; Haws, David; Studeny, Milan
  作者单位：University of York - UK; University of York - UK; International Business Machines (IBM); IBM USA; Czech Academy of Sciences; Institute of Information Theory & Automation of the Czech Academy of Sciences
  摘要：This paper deals with faces and facets of the family-variable polytope and the characteristic-imset polytope, which are special polytopes used in integer linear programming approaches to statistically learn Bayesian network structure. A common form of linear objectives to be maximized in this area leads to the concept of score equivalence (SE), both for linear objectives and for faces of the family-variable polytope. We characterize the linear space of SE objectives and establish a one-to-one ...
• Convex optimization learning of faithful Euclidean distance representations in nonlinear dimensionality reduction AI翻译
  作者：Ding, Chao; Qi, Hou-Duo
  作者单位：Chinese Academy of Sciences; University of Southampton
  摘要：Classical multidimensional scaling only works well when the noisy distances observed in a high dimensional space can be faithfully represented by Euclidean distances in a low dimensional space. Advanced models such as Maximum Variance Unfolding (MVU) and Minimum Volume Embedding (MVE) use Semi-Definite Programming (SDP) to reconstruct such faithful representations. While those SDP models are capable of producing high quality configuration numerically, they suffer two major drawbacks. One is th...
• Tight bounds on indefinite separable singly-constrained quadratic programs in linear-time AI翻译
  作者：Edirisinghe, Chanaka; Jeong, Jaehwan
  作者单位：Rensselaer Polytechnic Institute; Radford University
  摘要：Non-convex knapsack separable quadratic optimization with compact box constraints is an NP-hard problem. We present tight lower and upper bounding procedures that are computationally-efficient as the problem size grows. The lower bound is based on Lagrangian relaxation, and it is computed in linear-time. When the bound is not an exact global solution, a worst-case bound-quality measure is developed. Moreover, the lower bounding (LB) solution is improved to construct a feasible solution, leadin...
• Geometric random edge AI翻译
  作者：Eisenbrand, Friedrich; Vempala, Santosh
  作者单位：Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; University System of Georgia; Georgia Institute of Technology
  摘要：We show that a variant of the random-edge pivoting rule results in a strongly polynomial time simplex algorithm for linear programs , whose constraint matrix A satisfies a geometric property introduced by Brunsch and Roglin: The sine of the angle of a row of A to a hyperplane spanned by other rows of A is at least . This property is a geometric generalization of A being integral and each sub-determinant of A being bounded by in absolute value. In this case . In particular, linear programs defi...
• Random approximations in multiobjective optimization AI翻译
  作者：Vogel, Silvia
  作者单位：Technische Universitat Ilmenau
  摘要：Often decision makers have to cope with a programming problem with unknown quantitities. Then they will estimate these quantities and solve the problem as it then appears-the 'approximate problem'. Thus there is a need to establish conditions which will ensure that the solutions to the approximate problem will come close to the solutions to the true problem in a suitable manner. Confidence sets, i.e. sets that cover the true sets with a given prescribed probability, provide useful quantitative...
• An exponential lower bound for Cunningham's rule AI翻译
  作者：Avis, David; Friedmann, Oliver
  作者单位：University of Munich; Kyoto University; McGill University
  摘要：In this paper we give an exponential lower bound for Cunningham's least recently considered (round-robin) rule as applied to parity games, Markov decision processes and linear programs. This improves a recent subexponential bound of Friedmann for this rule on these problems. The round-robin rule fixes a cyclical order of the variables and chooses the next pivot variable starting from the previously chosen variable and proceeding in the given circular order. It is perhaps the simplest example f...
• Relative entropy optimization and its applications AI翻译
  作者：Chandrasekaran, Venkat; Shah, Parikshit
  作者单位：California Institute of Technology; California Institute of Technology; University of Wisconsin System; University of Wisconsin Madison
  摘要：In this expository article, we study optimization problems specified via linear and relative entropy inequalities. Such relative entropy programs (REPs) are convex optimization problems as the relative entropy function is jointly convex with respect to both its arguments. Prominent families of convex programs such as geometric programs (GPs), second-order cone programs, and entropy maximization problems are special cases of REPs, although REPs are more general than these classes of problems. W...
• A cutting-plane approach for large-scale capacitated multi-period facility location using a specialized interior-point method AI翻译
  作者：Castro, Jordi; Nasini, Stefano; Saldanha-da-Gama, Francisco
  作者单位：Universitat Politecnica de Catalunya; Centre National de la Recherche Scientifique (CNRS); IESEG School of Management; Universidade de Lisboa
  摘要：We propose a cutting-plane approach (namely, Benders decomposition) for a class of capacitated multi-period facility location problems. The novelty of this approach lies on the use of a specialized interior-point method for solving the Benders subproblems. The primal block-angular structure of the resulting linear optimization problems is exploited by the interior-point method, allowing the (either exact or inexact) efficient solution of large instances. The consequences of different modeling ...
• On the complexity of finding first-order critical points in constrained nonlinear optimization (vol 144, pg 93, 2014) AI翻译
  作者：Cartis, C.; Gould, N. I. M.; Toint, Ph. L.
  作者单位：University of Oxford; UK Research & Innovation (UKRI); Science & Technology Facilities Council (STFC); STFC Rutherford Appleton Laboratory; University of Namur; University of Namur
  摘要：In a recent paper (Cartis et al. in Math Prog A 144(2):93-106, 2014), the evaluation complexity of an algorithm to find an approximate first-order critical point for the general smooth constrained optimization problem was examined. Unfortunately, the proof of Lemma 3.5 in that paper uses a result from an earlier paper in an incorrect way, and indeed the result of the lemma is false. The purpose of this corrigendum is to provide a modification of the previous analysis that allows us to restore ...